Also because their links and bookmarks would have all failed.
It won't work because the HSTS setting the visitor got months ago told it not to.
In the webmaster tools, you want to get google to remove all references to the non https versions. Ensure https is up on all URL's, then use their tools to re-index everything and remove all references to http://
Are you saying you can't set up https on some of your URL's?
There's no issue with switching FROM HTTP to HTTPS: that's easy, just redirect them. The issue is if you have to switch back.
HSTS can't be enabled on plain HTTP so it's not possible to create the problematic scenario if you never had SSL enabled to begin with. The problem is switching from SSL to non-SSL, not the other way around.
Are you saying that you have applications that require HTTP port 80 only?
Also: HSTS applies to all ports once applied, not just 80/443. That is another important thing to consider before turning it on.
In that case, old visitors were rejected due to the policy. I wish I had set a lower duration.