One of the problems of using the pre-paid cards was brought to light recently in the Olympic incident of Harding/Kerrigan. Harding's husband bought one of the cards to make phone calls and they traced the calls back to him via the card, since you have to present valid ID to purchase those.

I have bought these cards without having to present any kind of ID. Most truck stops sell them (at least in the southeast). However, there could be other ways for them to figure out who you are, such as interrogating all the people whom you used the card to call.