Contacting Google's support brought the expected results and in the end I had to get a new IP assigned to the machine.
I have no idea how the IP got flagged as an Iranian one. Every geolocation service and whois stated clearly it's a dutch IP managed in the Netherlands. I only found out what was going on when I logged into my normal non-apps gmail account and looked at the activity list (I assumed I have been hacked). It showed one active session: my IP with origin "Iran".
/story time
This wouldn't be that bad, except Google is aggressively anti-user when it comes to this stuff, overriding both your headers and OS settings. (And alt text on things like Google Doodles always show up in the "geo" language, regardless of any overrides. Fortunately I bounce all my Google queries via disconnect, so this doesn't impact my search experience, just other Google sites usage.
How doesn't it? When your whole company IP range is flagged for "suspicious activity" and cannot use Google's search, your only option is to suck it up. No appeal process, nothing. You're not even told what "suspicious activity" so you could, you know, fix it.