I have a bare minimum of knowledge about how computer software works, probably just enough to be dangerous to myself and my equipment. However, I have an idea, probably very naive, that might work if you know somebody really knowledgeable.
If you go to Documents & Settings>All Users>Application Data> HP-APS and open the folder you will have a file labeled Registry Key, which contains the serial number that APS expects to find when you plug your colorimeter in. I would bet my boots that 1) you might be able to change the code to reflect your new serial number and/or 2) Find the place in the APS code that compares the registry key to what it is expecting, and that somehow these can be changed to get your new serial number to work.
I know it would take somebody really familiar with programming, and that it is not legal to deconstruct the HP software. However, it should be illegal for them to refuse to give you a solution for your problem, even though it was your mistake in throwing away the colorimeter. However, what would have happened if it failed in a different way, so that even if you had kept it it would not communicate with the software? I think either HP or X-Rite should honor that.
Actually, I never thought about the issue before and I shudder to think about what would happen if my colorimeter croaked and disabled my ability to use HP-APS!
A similar issue, I think, comes from Epson. My friend has an Epson 4000, their first 17" professional printer, which cost him close to $3,000 a few years ago. He upgraded to Windows 7 and found out that his printer is useless as Epson has abandoned making drivers for the new OS.