I had in the past gone to the microsoft site looking for updates (which are no longer available, microsoft does not support this system any more), and I got a re-cirtification thru the process. Somewhere there is a file on my computer of this re-cirtification.
?
Did you pay any money to Microsoft at that time?
For Win9x, if you don't have the COA and/or original media, there isn't actually any other way of confirming that you have a right to run the software.
Imagine if you'd bought a CD of your favourite band. You took a copy of the CD as a backup, then lost the original. You no longer have any proof that you owned the original; and I'm afraid no one would take your word for it. That reason has been used untruthfully too many times.
Going back to your problem, we have even less means of verifying the legality of what you're trying to do, and what we
cannot do is post information that would enable or encourage anyone else reading this public forum to breach copyright laws.
Tucker's eBay suggestion is your best bet - you'll find media and COAs aplenty there; some legit, some not. Take whichever choice your conscience and your wallet are comfortable with.
There's no point railing against the intellectual property system just because you don't like it by the way. These are the rules; this is the law. If you lose something and it's not insured, you would have to pay to replace it. You've lost something (your COA) and now you can expect that you'll have to pay to replace it. Sorry, but if you want to be legal, that is your only realistic option.