Developer YouMail saw its Visual Voicemail app withdrawn from Android Market, a move apparently driven by a complaint from T-Mobile USA.

The company received a message from Google’s Android Market support team, which said that “this application could be used in a way that is harmful to devices, networks or users.” It said that “specifically, we have received a complaint from T-Mobile that this application is causing adverse network disruption.”

In a blog post, YouMail said that not only had it not been contacted by T-Mobile, but that “none of the other carriers – AT&T, Verizon or Sprint – has ever complained about YouMail.” It was also critical of Android Market’s “guilty until proven innocent” stance, and that “at a minimum, if one carrier complains, why not simply turn off the app for that carrier – it’s only one checkbox – versus suspending it from anyone?”

The post continued: “YouMail isn’t some fly-by-night company.  We’ve been around for awhile, raised nearly US$13 million to build our technology and start growing our already ample user base.   We have taken well over a billion calls from over 75 million uniques.  That’s been as a result of three million plus downloads and well over two million users. If we had a problem, wouldn’t it have shown up much earlier as part of one of those billion calls?”

So far, T-Mobile has not clarified its position, with YouMail suggesting: “we hate to think this is simply anti-competitive behavior on T-Mobile’s part- simply because we’ve produced an innovative and dramatically better voicemail product than they offer, and that’s free on top of it.”