Here's my solution, but it will only work if you have my circumstance. My AT&T "Go" phone comes with an AT&T app called "Visual Voicemail". A few weeks ago I tried to set up this app, but the setup failed because I'm not a direct AT&T subscriber (see below). So I abandoned the setup. What I didn't realize was that my partial setup had suppressed my normal voicemail notifications. In order to undo this problem, I went to Settings -> General -> Apps -> Visual Voicemail. From there I did "Force Stop" and also "Disable" (two separate buttons). After disabling this app, my voice mail notifications returned.
FYI: I have an Android Marshmallow AT&T "Go Phone" (LG Phoenix 2). Even though it's an AT&T phone, I am on Consumer Cellular, which uses the AT&T network, but does not support all the AT&T apps. This failure here is part of what I dreaded when switching from a flip phone to a smart phone: too much complexity. You can do the most innocent thing and have no idea what the implications are for anything and everything else on your phone. Once you've done it, there are no clues and you can spend hours figuring it out.