This is a very frustrating problem. What makes it all the more frustrating is that the cause/solution can vary. Mike, you didn't mention the exact card or the exact cat version you are working with. You also mentioned that you did solve this problem before but can't remember how. This leads me to believe that my situation and your situation are not the same kettle.
However, for other's purposes, I'll simply provide my experience.
- Sapphire 9600SE
- Cat 3.4 (for interlaced resolutions over VGA out before the latest couple cat releases)
When trying to install the 3.4s, I was met with a 'video driver not found', 'load the standard VGA adpater first' error (also w/ a clean install). I searched all over this forum, other forums, M$ knowledge base and even e-mailed ATI and even started a thread about my problem having exhausted all cause/solution options I found. Note: if I'm not mistaken, I was met with the same 'search, it's all over response'. Obviously, for my particular situation, this was not true.
Finally, a kind soul over at Rage3D helped me out.
Here is a link to that help.
Bottom line, the 9600SE was built on the R360 core (the regular 9600 was built on the R350 core). The problem is that anything before 3.8 would not load on a R360 core card. The solution required hacking the driver. Once I performed the hack, the driver loaded correctly.
Just thought I'ld point this out to demonstrate that the sympton may be the same but the cause and therefore the solution can be different and far more difficult than many of the suggestions posted here.
Although this is probably not your problem because, like you said, you fixed it before but can't remember how, trust me, I will never forget my fix.