FWIW, I used to also have this with an old Sony BT dongle (this would also happen with most devices I ever tried it with, including my old N95).

I recently purchased a BH-214 and that symptom is definielty less noticeable; whether that's due to the newer protocol supported by the 214 (BT 2.1) or the fact that it has better connectivity or a larger buffer to prevent skips perhaps?