I cannot re-install my copy of Company of Heroes. I get the message that a version of the game is already installed and i have to use the addemove programs to get it removed but i already removed all traces of it. I even cleaned out the registry.

You can't copy the game files from the old PC even if you had it. Unless you have a friend who also has the same version of the game, you can't really do much with it.
I checked ebay out, and found several sellers who have the game for $10-15, but the best deal I found was from Steam (www.store.steampowered.com) They have the newer version of Heroes 5 for only 6.69 this week only, normally it's 9.99 but still a good deal, or you can get both expansion packs for $20.07 on sale (reg. 29.99).
It's a good deal but Steam is an online thing, so you download it instead of receiving a game disc. It's handy though, because if you ever need to re-install it, you can through steam, and you don't need codes or anything either.

I have Heroes of Might and Magic 5 Running on Win 7. There were many patches to install before this title worked(on my computer). Have you installed all the available updates for it?

Here are 2 sites that have the compatibility options:
http://techpaul.wordpress.com/2009/06/28/compatibility-tricks-for-old-programs-new-machines/
http://www.sevenforums.com/tutorials/316-compatibility-mode.html

If that does not work, you can also try to set up XP mode in Win 7: (Note: you need to have Win 7 Pro, Enterprise, or Ultimate for this one) Win 7 Home Premium does not support XP Mode.
http://arstechnica.com/microsoft/reviews/2010/01/windows-xp-mode.ars/

get the real copy of the game and it will most likely work or get a no cd crack from gamecopyworld.com

Read REQUIREMENT instructions on the CD cover leaf. If not open CD through your system locate Readme file of help or may be Manual read carefully and following the instruction, you will done. INSHALLAH

You have a bad copy from the company from the company itself.

It might be best to call the company on this one. Call Consumer Relations Answer Center at 800-432-5437.

first upgrade your directx version<if you dont know how, leave me a comment' ill help further>
and if it still gives the .dll problem then maybe the disk is damaged or has curropt data.

What the issue is and the only reason I know is because I have had the same issue. You need to go into the game options and change the graphics to a lower option. Your graphics are set too high. Also before you change the graphics right click on the desktop icon and go to properties and then click on compatibility and then click on run as administrator. If that does not work then change the graphics.

If it wont Eject try going into my computer right clicking the drive the Disc is inserted in and clicking eject, I find that works for me when my laptop screws up like that:P

Hello sir... The game is having some known issues with Vista. One way to overcome this error is, Install the game to a different directory other than the default.The default is "c:/programfiles/THQ/COHOF". U better create a subdirectory like "C:/programfiles/games/THQ/COHOF". If this fails, install it in another drive like D:/ or E:/.
Let me know if this helps.