What is the best way to find out how many records do not have a proper phone number in SQL Server?
It is one time task.
Write a small application or just select script, use C#, VB.NET, T-SQL...and analyze all patterns manually. 
Maybe you will find out common patterns by operators who inputed this data. Add an algorithm for every pattern. Apply your patterns to real data in a database. Remove all "wrong" records.

Luck.  

ADDED:

As option, you can use database of telephone numbers to check person2number validity if it's possible.