Thanks for the update Mark. Arthur's link doesn't get the security error any more, although it does go to a 404 error page (although maybe it's supposed to).
However we're currently still getting 404 errors on all requests sent to the API (the regular API, not Documents). I have no idea if this is related or not, but the timing suggests it is. My initial thought is it's security protocol related, however that had generated a different more specific error in the past.
This is using a key that still works if I go through the API directly, and from two different locations, so shouldn't be an IP related either, which suggests to me it's nothing to do with our account.
I'm trying to get more information, but as it stands every request we sent to the regular api is coming back with a generic 404 error.