I've been using Earthlink VoIP for the last 8 months. The first couple of months were pretty rough because my internet connection kept going out and thus the phone would not work. However, once I had them run a new cable line from the box outside to my house, I haven't had a problem since.
One thing to keep in mind, if you have a security system on your house, some VoIP providers are not compatible with Brinks Home Security. I've had some issues with Earthink and Brinks that they are working through now.
Good luck!