Just posting here to say that this issue was never solved and proved to be impossible to solve. Here’s what I tried:
1) Tried contacting Authorize.net Sandbox support. I sent them everything requested a few times. Their original response was that I have some kind of invalid scripting or HTML code in my response, which is not the case. I tested it numerous times and I am 200% sure the XML is correct. Like I mentioned before, the XML works perfectly when I submit it to API Live console (from developer.authorize.net/api/reference), but when I submit it from the site, it produces “Access denied” error.
I also copied the sample code directly from API Live Console, replaced name and transaction key with my Sandbox keys, and got the same result.
Also tried creating a very simple form on our site that takes the XML and submits it to the sandbox gateway. No matter what I tried, it gives access denied error.
Finally, I tried using PHP sample code for Authorize.net SDK, used my login and transaction key, and still got “access denied” error.
Oddly enough, it occasionally produces “Missing or invalid token” error.
2) I then tried checking my server configuration. Everything is correct. I also consulted out dedicated server support and they confirmed everything is good and up to date.
3) Tried doing it from a different IP, used different browsers to no luck.
4) Tried creating another sandbox account and repeating all steps above – no luck.
The only way to get it to work is to switch to production gateway and use production login and transaction key.
At this point I am just giving up, as I have to work on other projects. I guess Sandbox is no longer an option. Hopefully the production gateway won’t stop working like that in the future.