There are a number of different ways to find candidate's phone numbers. Google has a very large phonebook that you can search using rphonebook:Name it can also be narrowed down using the state abreviation for example, rphonebook:Tom Green MD Here is some more information on using Google's phonebook: http://google.about.com/od/googlebasics/qt/phonebook.htm
Zabasearch (zabasearch.com) is also very good at finding phone numbers.
As far as the legalities, this is public information, how you use it is a different story. I prefer email, but I'd love to hear others thoughts on this.