As far as I know, basically all browsers cache HTTP redirects by default, especially permanent ones. If you send your redirects without cache-control headers (and why would you do that for a permanent redirect), they may well cache them for a very long time. In at least Firefox, these memorized redirects are extremely persistent and seem basically impossible to get rid of in any easy way (having Firefox clear your local (disk) cache certainly doesn't do it).

This is a bad mistake. The theory is that a permanent redirect is, well, permanent. The reality is that websites periodically send permanent redirects that are not in fact permanent (cf) and they disappear after a while. Except, of course, that when your browser more or less permanently memorizes this temporary permanent redirect, it's nigh-permanent for you. So browsers should have a way to flush such a HTTP redirect just as they have shift-reload to force a real cache-bypassing page refresh.

(A normal shift-reload won't do it because HTTP redirections are attached to following links, not to pages (okay, technically they're attached to looking up URLs). You could make it so that a shift-reload on a page flushes any memorized HTTP redirections for any link on the page, but that would be both kind of weird and not sufficient in a world where JavaScript can materialize its own links as it feels like.)

Sidebar: Some notes about this and Firefox

I've read some suggestions that Firefox will do this if you either tell Firefox to remove the site's browsing history entirely or delete your entire cache directory by hand. Neither are what are I consider adequate solutions; one has drastic side effects and the other requires quite obscure by-hand action. I want something within the browser that is no more effort and impact than 'Preferences / Advanced / Network / Clear cached web content'. It actually irritates me that telling Firefox to clear cached content does not also discard memorized HTTP redirections, but it clearly doesn't.

If you have some degree of control over the target website, you can force Firefox to drop the memorized HTTP redirection by redirecting back to the right version. This is generally only going to be useful in some situations, eg if you have the same site available under multiple names.