What causes a "The search key was not found in any record" error in Access 2010?

The error message "The search key was not found in any record" was appearing on one record of a table in Access 2010.

I first noticed this when accessing that record via an update query, but later found that I also got the same error when trying to delete the record.

What causes this, and how can it be resolved?

It was just a database corruption, but I was misled by it only affecting one record. A Compact and Repair sorted it immediately.