iPhone 5 keeps asking for a voicemail password

Every time I listen to a new voicemail or delete a voicemail in the iPhone 5's visual voicemail, I am presented with the following message:

Password Incorrect: Enter Voicemail Password

My service provider is AT&T. I had an iPhone 5 for years that worked perfectly fine, but I had a battery swelling issue and was issued a new iPhone under warranty. That is when the voicemail problem started. Note that I have never had any trouble listening to a voicemail or deleting a voicemail... the problem is that I am presented with an annoying error message for no reason each time (listening and deleting works no matter whether I click "cancel", put in my correct voicemail password and click "okay", or put in an incorrect voicemail password and click "okay").

I went to the Genius bar in an Apple Store for support. The technician was incredibly rude and did not even attempt to fix it. He said it was an AT&T issue and suggested I go to a AT&T store. This was after he deleted all my open Safari tabs, repeatedly demanded I sign in to iCloud, and tried to "upgrade" my iOS against my will. (In my experience every time I "upgrade" any software I've found features are removed, problems are introduced, and my user experience gets worse, so I never "upgrade" unless absolutely necessary -- I say this as a power user who was a computer science major undergrad and have several computer certifications.)

At the AT&T store a customer service representative dialed a number and reset my voicemail password. This automatically texted me a new voicemail password. He entered it when the dialog box came up and that fixed the issue. However, I am not just interested in getting rid of the dialog box -- I am also interested in having a password of my choosing so I may remember it easily and access my voicemail without using my iPhone. Also, the AT&T guy neglected to mention that when he reset my password that made it so my voicemail box was no longer setup and erased my outgoing greeting. My friends were unable to contact me for a day until someone pointed out I needed to setup my voicemail box. Following my AT&T experience, I setup my voicemail box and changed the password to one of my choosing. This made it so I again was presented with the "Password Incorrect" message after every time I listened to a voicemail and every time I deleted a voicemail.

I have also tried the countless tutorials posted on support boards all over the web (including here), which basically suggest following the procedure that the customer service representative in the AT&T store used. I've re-setup my voicemail box quite a few times and have had no luck whatsoever picking a voicemail password of my choosing while also getting rid of the "Password Incorrect" popup message.

I'm unsure whether all of the people who have encountered this problem have simply decided to use the automated temporary password permanently or whether someone has successfully changed a voicemail password but failed to ever document it. It surprises me that putting their heads together no one at Apple and no one at AT&T can solve this problem.

Every time I see that popup (which is quite frequently), I want to scream!!

If anyone has any suggestions, please let me know.