However the backdoor still seems to be there which means the exploit is loaded in real time at the host.
Yes, it appears that the link to the *.rr.nu script is loaded dynamically. That is why the subdomain (part of the web address before .rr.nu) is always different. I also wonder if that is why the redirect only happens sometimes - I wonder if sometimes, the dynamically loaded script is actually broken, so it doesn't redirect. That could explain the random / intermittent nature of the redirect that some people experience.
Oz, have you engaged / contacted your webhost? This is clearly at least somewhat their problem, not necessarily yours. What say they?
P.S. For me, Google Chrome (on Windows 7) appears to work OK, even with my anti-virus turned off. You may want to try that to access the site without problems. Deleting history, temp files, etc. probably won't fix the problem for you if you are having the redirect problem (since the problem really isn't on your computer), but either using a different browser or updating your anti-virus (so that it can block the script from running) might help.
Another work around that worked for me is to put "gpsfiledepot.com" in your 'restricted sites' list in Internet Explorer. Then IE will block the script from running and IE will access the site without the redirect. You might not be able to download or upload files with gpsfiledepot in your restricted sites list, but at least you would be able to get to this forum to find out when the problem gets fixed.
Dave