If your going to completely remove avp2 for a fresh install, make sure you also clean the registry. Here is a step by step on how to do it. Some times the problem with the game is not the software, but the registry keys. It is easy to get corrupted registry values (game crash, bad restart, etc.) Just because you uninstalled the game does not mean that the registry is also removed. I'll repeat.... The registry remains behind after an uninstall. And because it isn't removed, unless you do it manually this registry key info will remain even after you put a fresh install onto your computer.
This is from a post on AVPlanet, but it's the one I followed when I had my problem and I found it again for McHardy to try.
------------------------------------------------------------------------------------------------------------------------------------------
SOMETHING's gonna be out of place even if not all of it. Finishing the job and reinstallin' sounds like the way to go. First, go into your Program Files folder, find the AvP2 folder, and delete it. Then you'll have to clean the registry to remove all trace of the game from the comp's memory. Be very careful doing this; erasing the wrong folder can result in Very Bad Things...
Cleaning Registry Entries:
1. Make sure you're on your desktop with all windows closed (print this post out if need be)
2. Left-Click on "Start" in the lower left
3. Left-Click on "Run"
4. Type in "regedit"
5. Left-Click on "OK"
6. Left-Click on the + by "HKEY_LOCAL_MACHINE"
7. Left-Click on the + by "SOFTWARE"
8. Left-Click on the + by "Microsoft"
9. Left-Click on the + by "Windows"
10. Left-Click on the + by "CurrentVersion"
11. Left-Click on the + by "Uninstall"
12. Left-Click on "{3EF79591-BF16-4CF8-8FF0-D8AD968228B1}"
13. Press the "Delete" key on your keyboard
14. Left-Click on "YES"
15. Retrace your steps until you reach "Microsoft"
16. Left-Click on the - by "Microsoft"
17. Left-Click on the + by "Monolith Productions"
18. Verify that you only have AVP2 in there(and not NOLF or any other Monolith game) If you don't have any other monolith games:
A. Left-Click on "Monolith Productions"
B. Press the "Delete" key on your keyboard
C. Left-Click on "Yes"
19. If you have other Monolith games in there:
A. Left-Click "Aliens vs. Predator 2"
B. Press the "Delete" key on your keyboard
C. Left-Click on "Yes"
20. Close the registry editor
21. Attempt to install AVP2
-------------------------------------------------------------------------------------------------------------------------------------------
Now install your updates, and other crap, UMP etc etc etc.