ちゃんと検証していないので取り急ぎメモです。
・URLは/example1/とする（example1.phpをmod_rewriteで書き換え）
・/example1/にアクセスされた場合、Cookieの内容を見て、
・画面Aを表示する
・/example2/へリダイレクト
のどちらかの処理を行なう
・/example2/では画面Bを表示する
・/example2/の画面B内からFormを/example1/へPOSTしCookie発行
・/example1/の画面Cを表示
お察しの通り、よくあるログイン画面です。
ところが/example1/→/example2/に何度かリダイレクトされた後、/example2/の画面Bからログインしようとしたところ、/example2/へリダイレクトしてしまうわけです。
まず始めにCookieが正しく発行されていないことを疑ったわけですが、これはすぐ正常発行が確認できました。
そこで、/example2/→/example1/の処理の冒頭で停止させてCookieの中身を表示させてみよう、と思ったところ、処理が始まる前に/example2/にリダイレクトしてしまうのです。
処理が始まる前ということは、/example1/のプログラム側の問題ではないということになるわけで、mod_rewriteの動きを疑う流れになると思うのですが、RewriteRuleをコメントアウトしてもリダイレクトが収まりません。
さてこれは何だろうと悩んだわけですが、ふと、同じ挙動をChromeで繰り返してみても再現しません。
となるとこれはブラウザの問題である可能性が高くなるわけで、Firefoxのアドオンを全てOffにして、再度やりなおしてみました。が、やはり変化はなく、さて、あと消せるものは何かあったかなと設定パネルを眺めていたところ、そういえばキャッシュは消してなかったなと気付き、全消ししてみたところ、サクっと正常に動作したというわけです。
結果として、FirefoxではLocationヘッダでのリダイレクトについてもキャッシュしている可能性がある（もしくはキャッシュする場合がある可能性がある）ということになると思います。
さて、そもそもLocationヘッダはキャッシュしていいもんなんでしょうか？
原典を見てみましょう。RFC 2616です。
10.3.2 301 Moved Permanently
The requested resource has been assigned a new permanent URI and any future references to this resource SHOULD use one of the returned URIs. Clients with link editing capabilities ought to automatically re-link references to the Request-URI to one or more of the new references returned by the server, where possible. This response is cacheable unless indicated otherwise.
The new permanent URI SHOULD be given by the Location field in the response. Unless the request method was HEAD, the entity of the response SHOULD contain a short hypertext note with a hyperlink to the new URI(s).
If the 301 status code is received in response to a request other than GET or HEAD, the user agent MUST NOT automatically redirect the request unless it can be confirmed by the user, since this might change the conditions under which the request was issued.
Note: When automatically redirecting a POST request after receiving a 301 status code, some existing HTTP/1.0 user agents will erroneously change it into a GET request.10.3.3 302 Found
The requested resource resides temporarily under a different URI. Since the redirection might be altered on occasion, the client SHOULD continue to use the Request-URI for future requests. This response is only cacheable if indicated by a Cache-Control or Expires header field.
The temporary URI SHOULD be given by the Location field in the response. Unless the request method was HEAD, the entity of the response SHOULD contain a short hypertext note with a hyperlink to the new URI(s).
これを見ると、
・301：「別のものを指定していない限り」キャッシュ可能
・302：Cache-ControlかExpiresが指定されている場合のみキャッシュ可能
となっています。（「別のもの」って何？）
ということは、301でリダイレクトしたらキャッシュされても文句は言えないわけです。
そもそも「Moved Permanently」なわけですし。
ここで、あー、と思い出しました。
そういえば、何を思ったのか、リダイレクトを301で書いていたのでした…。
ということで、FirefoxはStatus301ヘッダをキャッシュしている可能性があり、かつそれはRFC的には正しい挙動であるということになるかと思います。
自分が悪いからしょうがないというオチなんですが、確かにキャッシュすれば遷移は速くなるというブラウザ側の都合も納得しつつ、これはキャッシュしてほしくないところだなーと…。