Proxies don't perform the redirect themselves, so they don't need to support it, they just need to pass it through like any other 3xx.

The last UA I saw that didn't support 303 was Netscape 4.

Body of the redirect response should contain a link to the new page. This way even time travellers form '90s will be able to reach the destination page.