The issue is not solved yet, but I wanted to let you know that Paypal has finally realized it could be their problem. Here is their response this morning to the latest ticket I filed:
"Thank you for the information provided. I have escalated the information to our internal team again for them to check further on this. The internal team would have full access to check as they can look through the database logs and what is triggering the issue. I do not have much access to check on this but I was able to replicate this issue by the address you have provided. I do appreciate your patience over resolving this issue and will update you once I have information from the internal team."
I will let you know what happens.