The tool only needs to be run in safe mode if Avast doesn't uninstall cleanly via add/remove programs.
Deleting prefetch files would do no harm. (So you can't blame your wife. Sorry.
)
That said nothing should really be deleted unless the user knows what it's for. Is it possible anything else was deleted?
This is starting to possibly sound more like a malware issue, or maybe a registry issue..I don't really know.
If no programs will run on it your options become a bit limited. Sorry, I have no experience with re-installing an OS on a HP machine without a disk. If you can borrow an XP Home installation disk, a repair install might be possible.
One thing I'd look at doing - if no-one else posts with more informed ideas - is to try a BART disk. This would need to be downloaded and burned using a clean and working computer.
Below are links to a couple.
Avira (Direct Download),
DrWeb (also have a look at the "how it works" link on that page)