Using batch update via profile allows the email address to be deleted from contact records which have no other data (ie. email is used as the name). This leaves null records which cause duplicate matching problems. Doing this is disallowed via the UI and Batch update via profile should also not allow creation of null records.
I've reproduced this on CiviCRM 1.6 and on the CiviCRM 1.7 demo.
In our case a batch update of 100 records to delete hard bouncing emails created 6 null records and left the others not displaying the names. This was cleared by editing and saving the records with names and deleting the null records. They all show up at the top of a blank search with no name.