SOQL Query by External ID is missing records

I'm having a problem consistently querying an object by an external id. When I do a SOQL query that has a queryplan that uses an index on the externalID, the record can not always be found. It is as though the index is corrupt, but I have no way to force a rebuild.

My minimum example:

I have a field named PID on the standard Contact object. PID is defined as autonumber (format p{00000}) and flagged as external ID.

For brevity, assume I have exactly two contact records with salesforce ids of 'record1' and 'record2' (I'm not going to try to type the real ones). The name fields of these two records contain 'name1' and name2' respectively.

Through the salesforce.com UI, I can search the names and find

Name: name1 PID: P00000 

and

Name: name2 PID: P00001 

In the force.com developer console,

query: select id, pid__c, name where name='name1' result: record1,'P00000','name1' query: select id, pid__c, name where id='record1' result: record1,'P00000','name1' query: select id,pid__c,name where pid__c >= 'p0000' result: record1,'P00000','name1' record2,'P00001','name2' query: select id, pid__c, name where pid__c = 'P00001' result: record1,'P00001','name2' 

****** BUT *******

query: select id,pid__c,name where pid__c='P00000' result: <no rows> 

There are actually about 8000 rows in this table with a bunch of other fields and externalIDs, but no duplicate PIDs since that's an autonumber field.

I haven't been able to detect a pattern as to which records can and cannot be located by PID. Some, like P00001 in this example, can be found and some, like P00000, can not. If a record can be found by PID once, it can always be found. If it can not be found by PID on the first attempt, it will never be findable.

Ideas, anyone?

Thanks -Jim