I'd recommend using a service/tool that implements fuzzy matching dupe detection. If you're on SFDC they recently released a new duplicate management feature where you can implement fuzzy matching rules.
If you have a tool like RingLead, you may be able to surface and merge records more easily by Name and Company, assuming the lead provides you enough clues.
I also recommend DemandTools. We were using it until recently and it was a godsend.