I came across this issue few months ago when I bought an Android phone (HTC Wildfire) and of course I needed Skype to be there as I’m using it at work. I was aware that Skype team already released an updated Skype for Android app that supports low-resolution displays (320×240 in this case) and my device was listed on official websites as supported one. But guess what? I even couldn’t find Skype app in Market on my phone, only some chinese apps and searching it by process name returned me 404.
Then I tried to use desktop web version of Android Market to install it in some tricky way (I never “rooted” my phone, in fact I don’t like it (and actually don’t need it)), but that was also unfortunate experience, but at least I’ve got some message like this:
Wow, at least it explains the part of the problem. However I was able to install Skype on another Samsung Android phone with the same carrier and country. And after a minute I realized I have foreign Vodafone card from my last trip. And indeed, with this SIM I easily found Skype app and downloaded/installed it on Wi-Fi. And it even found updates for some Android core apps like Youtube and Google Maps!
So we can conclude that Google is limiting user experience depending on country and carrier, which is bad trend as for the user, taking into consideration internet as a global network, this limit is very confusing, especially for free apps. So if you have another SIM card, try to insert it and search for your app again.