Hi, I've experienced this problem too, I'm on Orange and have a Hero.
The title I wanted to buy was "Robo Defense", there's a demo version - "Robo Defense Free". Searching fails to find the full version. My friend on T-mobile (G1) has no issue in finding it.
I just did a search for PicSay Pro and could only find a free version of it. Seems to be the exact same problem.
I was under the impression that it might be something to do with the issue raised here:
UK user cannot download US Paid Apps! Help! (only UK made apps) - Android Market Help
But your reason sounds much more likely since I can actually see some apps priced in dollars.
Have you spoken to anyone official about it yet? I'd call Orange but for the fear of speaking to someone who has no idea what I'm talking about and ending up explaining the problem over and over. I might fire off an email or something, can you reveal your sources? Also, where are the petitions?