There is the "Event Viewer" but that's not really a database. You could try any MRU lists, if you haven't disabled them on these work machines, but personally I would have used Add/Remove myself.
Are you saying that users can install software themselves?
Why not reinstall XP? That way the next user gets a fresh OS.
Mark
In Windows XP, the Add/Remove feature is notoriously wrong when it comes to the date a program was last used. The hard drive on one of our office PCs is almost full. Defragmenting takes forever and doesn't help very much. I want to remove software the former user (who no longer works for us) seldom or never used. HELP!

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic