Successes from afar; rules or exception?

Does not having a physical presence in my target market serious impede my potential?

It can, if your business needs any of the following:

• corporate partnerships, such as OEM deals, co-marketing, etc
• "trust" from end users that are skeptical of buying from an overseas company due to shipping costs / uncertainties about warranty laws / hesitation to send credit card info overseas. (In my experience, when it comes to virtual goods the clear majority of end users are not like this. Physical products are another matter.)

Having said that, I know of several SaaS companies in Scandinavia who sell globally, and have a large share of their customers in the US. The "credibility" of their country of origin has never been something they've complained about. Their complaints are more practical -- less access to venture capital, hiring people is relatively expensive, limited supply of skilled software developers, that kind of stuff.

You could do a survey in your target market. If hard facts show that they care about this, and consider it negative, then setting up a shelf company to handle sales is not that hard. If on the other hand your customers don't really care, then don't complicate matters.

Off the top of my head, I think that ABBYY, JetBrains and Kaspersky Lab (all Russian companies) do pretty well. If you're selling software on the Internet, it probably doesn't matter that much where you are physically located. Marketing and the quality of your product is more important I'd say.