The Android Market is a mixed blessing; on the one hand, I much prefer the near-instantaneous publishing time for applications. It makes things a lot less stressful; if there's a terrible bug you can fix it quickly instead of having to go through Apple's approval process all over again. On the other hand, it has a number of bugs and limitations that are frustrating.
One of the most common support emails I get is "why can't I find your app on the Market?" This is a sad email, one of a customer lost; and over time (from contact with Google or perusing the net) I've come up with a good list of reasons why customers can't find my applications. Here it is, to help others diagnose the dreaded customer-who-would-be (in order of most likely to least likely):
The customer has an older version of Android that your app does not support; for example, if you support 2.x but the user is on a 1.5 phone.
Paid apps are only supported in some countries; if the customer is not in one of these countries, then you will not be able to find or purchase any paid applications. The list of supported countries can be found here.
Note that the customer can't simply move to a different country, either; this limitation is dependent on where your phone plan originally comes from. (Thanks to a European customer who confirmed this for me on a business trip!)
The customer is using a Google Apps account, rather than a gmail.com account. This can either cause the app not to appear at all, or in some cases make it unpurchaseable. More details can be found here.
The customer has a recently released phone and Google hasn't "fingerprinted" that device yet. This blocks all paid apps from that device. The only solution is to wait until Google fingerprints; it was kind of a pain with HTC Desire, at it took them a few weeks to get around to it.
The customer is using a non-standard build of Android (that is, rooted and installed a custom ROM). Some of these builds cause the Market to malfunction and fail to display paid apps.
The customer is using an Android Developer Phone and your application has copyright protection enabled. ADPs aren't allowed to view copyright protection applications. More info here.
This is by far the least likely situation, but you can't buy your own app under the same account as you published from!