I never worried about the free email account issue because we screen the orders for fraud.
Some of the simpler things you can do to kick the fraud is:
1. require the CVV2 code which means card in hand or a cloned card, but that's less likely
2. use Verified by Visa which requires a pin #
3. offer people using those email accounts PayPal, which validates their members
The problem with phone verification now is everyone uses cell phones.
When it's a landline phone # calling directory assistance can confirm the phone # matches the address given, then calling the phone # can confirm that they actually placed the order.