Eu tenho o mesmo problema. Parece ser um comportamento deliberadamente codificado que, se o firefox se conectar à versão https de um site, ele nunca mais se conectará via http.
Limpar histórico e cache nunca resolveu o problema para mim, mas se você apagar completamente as configurações do firefox (rm -rf .mozilla no Linux) ele permitirá novamente que você acesse a versão http do site. Então, ele é armazenado em algum lugar nas configurações do firefox.
Isso acontece comigo com absolutamente nenhum cabeçalho de redirecionamento do site, sem cabeçalhos de segurança de transporte estritos e absolutamente sem addons do firefox.
Eu vi muitas pessoas postarem esse comportamento como um bug contra o Firefox. Eu ainda não vi nenhuma reação além da descrença. É difícil consertar um bug quando os desenvolvedores estão em negação. A melhor coisa que posso sugerir é remover completamente todas as configurações do firefox quando isso acontecer. Quanto aos usuários finais, eu acho que você acabou de dizer a eles para não usarem o Firefox.