Is this all icons or just a particular icon, are they Shortcuts?
If it is just one or two Shortcuts, right-click on the Shortcut icon and look for the options via Properties to open Maximized.
Otherwise, some general things to try.
See if System Restore will get you back to a restore point before your problem with Explorer.
Try Safe Mode (Do you have this problem in Safe Mode?).
Run the System File Checker program from the Run Box by typing.....Sfc /Scannow in it and have your XP CD handy.
HOW TO: Verify Unsigned Device Drivers in Windows XP
If they don't work you could try repairing windows by running it over itself. You will lose all your windows updates but your files will be untouched.
How to Perform an In-Place Upgrade (Reinstallation) of Windows XP (Q315341)
Also consider this.
Removing adware & spyware
faq608-4650
Try the free version of "Ewido"
Windows Defender
AutoSizer (freeware).
AutoSizer automatically resizes any window you specify. For instance, some web browsers open up in a non-maximized window. Using AutoSizer, you can set those windows to automatically maximize every time they’re opened. It works with almost any program, including web browsers, Notepad, etc. AutoSizer stays running in the system tray (next to the time), so it stays out of your way while it works.