A SOQL Query uses a filter that is unique and indexed. It may return incorrect results in the Sandbox.
SELECT Id,External_ID_vod__c,Name from Address_vod__c where Account_vod__r.External_ID_vod__c = '123456'
No results are returned even though there are actual results matching there.
This is a Salesforce-known issue. It is due to an index on the custom field which gets corrupted during a Sandbox refresh.
Remove and Recreate Unique properties of the custom field External.
Salesforce Help Documentation: SOQL Queries returning incorrect results in sandbox