Worked with two over ICC and the phone for lengthy (1-2 years each) durations of time. Really good experiences, both. Stopped lessons for financial + motivation reasons but would have stayed on with either of them even though I'd never meet them face-to-face.
Both of these instructors were very good "socratic method" teachers who wanted you to come to your own conclusions while they nudged you when you went wrong and forced you out of your comfort zone. Both of them used lessons to go about fixing my often-made-errors as well as "unclogging" the gunk in my "thought process" plumbing INSTEAD of just broadcasting loads of information and expecting me to absorb it like a sponge.
So I was probably quite lucky. From what I've heard, a majority of players who claim to be able to teach online often are just strong players who either can't teach/ don't put enough of their heart into it. I once got a free "trial" lesson from a NM coach on a new "rival to chess.com" site and he just played two blitz games with me and asked what openings I played ... and then told me to play something else ==> a terrible fit given what I wanted + liked in a coach. Not to mention he answered a phonecall in between and I could hear him messaging other people online while talking to me. So ... yeah. :)
So bottom line, shop around and if you are willing to pay, do not skimp as the good ones charge just as well :)
Where I live, I can't find a chess coach for lessons in person so I'm considering lessons over the Internet.
If you have had lessons over the Internet/Skype, can you share your experiences with me? Good/Bad/Meh