Great to hear youíve managed to solve the problem but best read this to make sure is doesn't happen again.
By coincidence, I had a Compaq Vista laptop in the shop this week with exactly the same problem of the Recovery Partition going into the red.
I did almost what I suggested you try but with the variation that I backed up the Recovery Partition for safety sake and then deleted the contents of the original Partition completely (yes, we did have the 3 DVDs). This worked fine but when checking it again a couple of days later, guess what? It had started to fill up again, with 5 GB of HP diagnostic tools! It looks to me that, out of nowhere, HP support has started to churn out some tool updates for Vista and missed the point that they will overload the size of the Recovery Partition. Iím not surprised - little good appears to come out of HP support these days.
To prevent this problem coming back to your system again my advice is to go into Control Panel > Programs and Features, and remove the HP updater program completely Ė itís no use to man or beast now anyway and that will kill the little varmint off.
As general maintenance, Iíd also download these two tools (from some cleaver Brit programmers) to keep your system running cleanly:
CCleaner, which is very safe and only does good (but donít use the registry cleaner section as such things are always the work of the devil!)
Defraggler, also very safe and the best defragmenter Iíve used: