I'm not sure I have the "cause" of this issue diagnosed correctly - but it seems like bringing up the "problem" records in Edit mode and saving them fixes that record.
To recreate- using sandbox.civicrm.org :
From Find Contacts - enter "zope" in the Name field and search.
Note that Zope, Bill has no data in the address, email and phone columns (row 1).
Now Edit that record - and Save
Now search again on "zope".
I think you'll see that the data is now populated for that row (I did this with contact 17 - Zope, Sam - and his row does show the data).