|Extending on Ed's bootable disk idea:|
Get yourself a copy of knoppix or ubuntu (or even puppy) - all linux variants on a CD/DVD.
Boot with that - set CD/DVD as first boot device of course.
Go on-line to: trend.com locate and run their free housecall utility. Let it do a full scan. Anything that is by chance quarantined on the local HD as a result of the scan - delete it (not likely to happen but who knows?).
Then reboot as per norm and see how things is... (You may be lucky and find the nastyhas been eliminated...)
knoppix.com, and ubuntu.com have free ISO download for their respective versions. Save to HD, bun to a dvd; boot with that DVD as above etc...
gives a link to puppy...; and again once you have burnt the DVD boot with that if you prefer?
re' can't get to recovery screen - explain that bit further?
And have you done a search at HP/Compaq - support - download area to see if you can download a recovery disk set (ISO); or contacted them directly?
Also again on Ed's tail re' safe-mode: can you get that far and if so with networkng? If you can, disable system-restore then run an on-line sccan as above; and also perhaps using a similar one at avg (I think they offer similar freebie)? Do not re-enable system restore - until you are sure system is clean...