There are many reasons why this can happen, but in this case it was a problem with the integration between MSN Messenger 7.5 and Outlook 2003.
CTRL+ALT+DEL showed me that Messenger was using 125MB of RAM. Stopped the service and uninstalled Messenger and Desktop Indexing (the user didn’t need these things) . Rebooted and it was fine and even faster than before.
