Awesome topic, and surely one of my favorites
Colan shared some solid thoughts indeed, here are mine (some might overlap though):
1) Are there certain sites that you start with?
Yes, we start with the websites that have been proven to have the largest business database. These include:
Google
Bing
Localeze
ExpressUpdateUSA
Yellowpages
Yahoo
Citysearch
Superpages
Manta
...
The list goes on. As most of these tools are covered either by Yext, or by GetListed.org, we use them to fast scan through all of them. After this we usually use Whitespark's Citation Finder, Bright Local's Citation Tracker, and in some more serious cases - Sweet IQ. All of these usually return different results, so it's not rare that this way we find duplicate listings, or listings on websites that if we use just one of these tools we wouldn't find. We save the URLs of all listings that we find this way on a master spreadsheet and we use different coloring for different types of listings, so that we could more easily figure out what to do - color X for listing that have problems, color Y for listings that look fine, and color Z in the cases where on particular websites that has been predetermined to be valuable in the particular niche there is no listing for the business (neither correct, nor incorrect).
2) What do you do when you find listings that may be claimed and the client doesn't know by who, or even how to access them?
In the majority of the cases contacting the websites by phone would be the easiest way around this. They usually either set new account for you, fix the listing by themselves (as per your input), or delete the listing. However, there are some "stubborn" ones like Yellowpages for instance, where dealing with such cases is a little nightmare. But these cases are generally very rare.
A few articles that might help here:
Local Citation Building Study Part 2: What the Pros Think | Local Search Marketing Blog by NGS
Local Citation Building Tools | Local Search Marketing Blog by NGS
Removing Duplicate Listings from Different Business Directories
Hope this helps!