Well, I guess that the only thing left would be to call up Bethesda's technical support department, or try looking in the forum on Bethesda's web site.
Perhaps someone there had the same problem as you and has solved it.
EDIT:
This game installs that 'Microsoft Games 4 Windows' thing. Supposedly there was some kind of problem with it and it needs to be updated.
This might be the whole problem. The Version 1.5 Fallout 3 patch writes new files for MG4W, so maybe that will fix the problem if you haven't updated already.
The MG4W thing must be uninstalled from Control Panel because it stays even after you uninstall the game. Perhaps you can try uninstalling the MG4W thing and then re-install the game (which will also install MG4W), then try playing the game. Maybe the old MG4W files left over from when you initally installed the game are no good.