Can the HTTP status be set with the redirect tag
That should work fine.  I just did a test in a simple template with:

{% redirect "http://google.com" 301 %}


And I can see it's a proper 301 redirect.  Try clearing your browser's cache?