Something else I haven't noticed asked yet,

Do you only see this problem when connected to the internet, or does it also type slower then normal when in other apps (like word, notepad, etc) when not connected?

If its not only when you're connected to the internet but is just more noticable when connected, then it could be that you have other apps running in the background causing your system to slowdown - things like CTFMON.

Or it could be even a more basic thing like defragging your system, when was the last time you did that?

But - if ONLY when connected to the internet, I'd go with the others suggestions and suggest you run a virus scanner and download an anti-adware/malware app such as spybot-S&D...