I'm in Boston and my co-founder's in Europe and it's worked very well so far (10 months and counting) despite the distance.
BUT we have a long history (grew up together, started a company together in the past) which I think is the #1 reason why distance has not been an issue.
Even with that history, he splits his time, spending half of it here in Boston and the other half in Europe. Plus he and his wife plan on moving back here in the next several months.
I realize Skype is amazing (esp video chat!) and tools like Basecamp/ Trac/ Wikis make collaboration easier, but I think there's no substitute for knowing your co-founder inside and out and working in the same room with him/her on a regular basis.
And the thought of starting a company with someone I've never met just scares me. :)
Just my two cents,
Reading all the answers there seems to be a pattern. Where either there is some sort of shared history or the founders have worked together in some capacity together prior to moving away.
A question I would ask would be 'is this your first startup'?
If it is then you should do your level best to get a co-founder who you could physically meet with. Especially if your product/service is targeted towards one particular location eg. Europe. If you are currently based in the US and your partner in Europe there will be a huge strain on him to both keep up and do biz development.
If this isn't your first startup then I guess you must have already experienced how challenging it is to keep the motivation levels high and keep moving forward when the chips are down.
Founders in different location adds further pressure to a startup environment where there is already a ton to begin with. So I would do my best to avoid it as much as I could.
There are advantages in not having to meet with partners regularly. Like not getting on each other nerves, at least not in person.
But accountability is lower, in person communication can not be replaced entirely, and there is always the risk of your partner simply disappearing, especially if you never met him. Not that it can't happen with a friend you have known forever but
Remeber, this is the internet, never met him means he could be an alien zombie nazi, trying to take over the world with your competence and assistance.
My co-founder and I worked together in our old jobs. After that we shared an office for a year before he moved back to Australia with his family. Now we work together from different countries in vastly different time zones (I'm in the U.S.).
In my opinion, it is much, much harder to work virtually than to share the same physical space. For anything requiring design or brainstorming, it's much easier to share a common whiteboard than to collaborate via chat or email.
The great thing about having worked closely together for several years is that you get a sense of your co-founder's work habits, personality, and sense of humor. Understanding these things makes it much easier to work together over the phone.