would have been too easy

do the following - note that the cryptic file names listed below are for the seperate games - you might want to look through all the (hopefully not too many) directories in install shield installation information and delete those that contain civilization files - if in doubt just move them until you are finished reinstalling and move them back afterwards. Also if the directories where you need to delete stuff manually do not exist but gold edition directories do - delete those

Tell me if it helped
install the most recent version of DirectX 9c from
Microsoft
then do the following for a clean reinstall:
Uninstall and Reinstall Gold
Try to follow this order when doing stuff:
Use Control panel to uninstall Beyond the Sword, then Warlords, then Vanilla
Delete "...\documents and settings\<username>\my documents\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\my documents\my games\warlords" manually
Delete "...\documents and settings\<username>\application data\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\application data\my games\warlords" manually
(note: application data is a hidden directory so you need to configure windows explorer to show hidden files, also these directories in application data are sometimes removed by the uninstall routine)
Delete "...\Program Files\InstallShield Installation Information\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}" (Civ4)
Delete "...\Program Files\InstallShield Installation Information\{3E4B349F-10B5-4586-9D99-489A90A8B228}" (Warlords)
(note: InstallShield Installation Information is a hidden directory so you need to configure windows explorer to show hidden files).
Install Gold Edition