I really like your recap...

what is your datasource?  I have a really vague recollection of something about desktop datasources (i.e. Excel) not allowing subscriptions to show up.

Double check that the password is embedded (aka not prompt) within the datasource connection.

1. What version of Tableau Server?
2. Check the permissions at the Project and workbook levels.  If the report is a single view then look at the permissions for that particular view.

You mention VizAlerts (Matt Coles) so do you have your VizAlerts schedules set up as well?  Some of my regular working subscription schedules with VizAlerts in the red box:

Are users reaching the reports directly from the Tableau Server or through a URL that may have command line parameters?

in addition to your #1 item, are the email settings fully configured at the server level?

Looks like you've covered all your bases! My next step if I were troubleshooting would be to ask for screenshots of each of these things to show that they'd been done and give me a change to verify that there wasn't anything funky going on in any of the screens. Or do a screen share where we could walk through it. So if I were you, Aaron, I'd go through the list one final time and double-check everything, then send it in to support if you still can't figure it out. If you post screenshots here, we'd be happy to look at them too, I'm sure.

It looks like you read the Manage Subscriptions so that's good.

From the Administration Guide I did a search.  This page showed up:  http://onlinehelp.tableau.com/v9.1/server/en-us/help.htm#subscribe_trouble.htm?Highlight=subscription

No subscription icon

It's possible to see a view on Tableau Server but be unable to subscribe to it. This happens for views with live database connections, where you’re prompted for your database credentials when you first click the view. A subscription includes a view (or workbook), data, and a schedule. To deliver the data piece, Tableau Server either needs embedded database credentials or data that doesn't require credentials. Where live database connections are concerned, Tableau Server doesn't have the credentials, only the individual users do. This is why you can only subscribe to views that either don’t require credentials or have them embedded.

You may also be able to see a view but be unable to subscribe to it (no subscription icon) if Tableau Server is configured for trusted authentication. See Subscription Requirements for more information.

I would recommend you find a viz that is not showing the desired subscription icon.  Check it's specific permissions at the lowest level.  If those check out then download the workbook and open it.  Now go through the publish process but visually check the Authentication section:

and make sure you see Authentication set to Embedded password:

If you this checks out then simply Cancel out of the publishing process, otherwise republish with embedded password.  Also, if the workbook is a lesser version then republish it.

If this doesn't work then are your workbooks connecting to a published data source?  If so and they are older (published under an older version, for example, 8.1) then republish them with Authentication set to Embedded password:

Please show us the full URL (you can exclude the server/domain bit ).