1. Dialup or Hispeed? Have them put the mouse arrow on the Dialup monitor icons to check connection speed, i.e. about 46,000 or 32,400?
The point being that the modem drivers may have kicked back to a slower "max connection" in Modem Properties.
If the speed (bauds per second)is up there, then they must be talking about page display speed, which may have been slowed by some security checking application, such as MS Antispyware, and they may have to live with it or go back to being invaded or vulnerable to invasion by spyware-malware.
If Hispeed connection, same deal about the Antispyware deal, or the DSL modem drivers may have changed. You can look at XP's "rollback" to revert to previous drivers.
2. Without more specific crtical update numbers, which you've looked at, can't say much else. Where there any driver updates that messed into the batch? At this point, you can submit a list of the critical updates for better answers.