None of what you've said surprises me. I would expect you to notice a gradual slowdown to unbearable over the next 6 to 12 months. It's typical Windows behaviour.
Add/Remove Programs is a nightmare. If it freezes up at all or anything while removing software the chances are some stuff will be removed, but will stay on the list, and when you try to remove it it will say it's already removed! Also a lot of programs don't clean up properly after themselves, so you'll need to delete them from startup items yourself.
As for deleting an icon on the desktop and it being gone for all users this is a common thing that confuses people, but yes it is normal. Basically, your desktop shows you icons from two places:
C:/Documents and Settings/All Users/Desktop
C:/Documents and Settings/USERNAME/Desktop
If you delete an icon from your desktop and it is in the 'All Users' desktop, then it will be deleted from everyone's desktop. If you want something in your girlfriend's desktop but not yours, you need to make sure it's in the desktop related only to her username, rather than the 'All Users' one. Typically, when you install a bit of software it will put its shortcut into 'All Users' but when you right click the desktop and do 'Create Shortcut' it will usually put it into the folder for the desktop of the user you're logged in as when you do it (unless you've used an app to change this setting).
Hope that is, at leasdt, a bit of help for you. Next time buy a mac.