You are free to not buy it my friend, but one day Paypal will give you the hammer and you will see just how believeable this is. In fact, there are countless threads online with the same story. You've never had a rep from a big company say something and you call the next day and they have no record of that? It happens at least 3 times a year with my cellphone company, you must be very lucky!
All good. If you'd used your original HN handle rather than making a new one for this issue, and mentioning who you were and what your business is, that may have gone further in validating your story (for me at least).
Took me 2 minutes to find your post on Twitter, and from there your old handle and submissions on HN and details of your business. Your story now has more credibility. I'm all for anonymous opinions and discussion, but when it comes to seeking support in complaints against another company, it's best to disclose who you are (in my opinion).
I did say it, but I didn't say that. "Magically there was a record" meaning they had it all along and that customer service departments of that size are routinely slow to update or make simple mistakes, not that it fell from the sky as a small sliver of corroboration for OP's story. You'd sooner believe a stranger is lying from a throwaway account on a random forum than a phone jockey making a mistake...but at least you're happy.