OwinStartup not firing

If you've upgraded from an older MVC version make sure you don't have

  <add key="owin:AutomaticAppStartup" value="false" />

in your web.config. It will suppress calling the startup logic.

Instead change it to true

  <add key="owin:AutomaticAppStartup" value="true" />

I realize you already mentioned this but sometimes people (like me) don't read the whole question and just jump to the answers...

Somewhere along the line - when I upgraded to MVC 5 this got added and I never saw it until today.

Make sure you have installed Microsoft.Owin.Host.SystemWeb package in the project. This package is needed for startup detection in IIS hosted applications. For more information you can refer to this article.