Is it REALLY piracy if he's already paid for it?
Yes.
I mean at it's core, what he's looking for is essentially just a few dozen byte string. If the end result is the same if it's one string versus another, does it matter?
In the grand scheme of things, does anything
really matter?
I suppose this is more a philosophical question than a practical one.
As per my last comment, I agree with your comment.

Could it be likened to buying a music cd, losing it, then downloading the same album?
Yes, absolutely. Again, piracy.
The difference is that electronic media can be copied, with
no detriment to the source material. (By copying that CD, movie, or program, you're not physically damaging the source in any way, are you?) Thus, the only damage being done is really to the developers, manufacturers, distributors, etc. etc. because they do not make any money on these duplicates. Horribly damaging on a mass scale, for example, when someone uploads a movie before it hits theatres, and causes people who would have paid to see it to watch it for free and decide it's not worth the money to support.
Is it
morally wrong to copy the program you purchased, especially since you've exhausted every avenue to try and get the replacement code? I would say no. Is it legally wrong? Sadly, the Law says yes.