In Firefox, the 301 redirect cache can be used as a form of cookie, which is not cleared by clearing regular cookies. One has to clear the entire cache to get rid of these redirects. See https://rehmann.co/projects/301-Redirect-Cookie/ This has privacy implications as this method can be used by sites to store permanent information, even when the user has disabled or cleared cookies. The 301 cache for a site should probably get cleared when the cookies are.
(more general bug)