The issue was related to PHP. This was a mediatemple GS server and it had the PHP set to 5.3.27 FastCGI. I had to change this to 5.3.27 CGI (stable) and this seemed to clear up all the issues. Hopefully this may help someone in the future as the issue was unexpected and not clear what the issue was.
I've created a really basic extension to bypass the default message. It redirects to an account page on login and the home page on logout but this could be modified to point to any URL (i.e. a custom message landing page)
I've included a link to the download but should that expire you'll need to copy/save these two files into system/user/addons/loginbypass/