It turns out that if you change rate plans on your iPhone, they need to remove the old plan and add the new. In this process all of your Visual Voicemail is lost into the abyss that is AT&T.
Even dialing 1 from your iPhone won’t retrieve these lost voice mails. There seems to be nothing that AT&T can do to get them back either. Lesson learned today, don’t change rate plans unless you really need to.