Q After reading about Disk Utility, I tried verifying my startup disk, only to see the message that the verify failed due to ‘Keys out of order’. The Mac was working fine. What do I do next?
A This is a potentially serious problem, and likely to require that you re-initialise that hard disk to fix it. At your earliest opportunity, make an extra backup of important documents, and ensure that your Time Machine backup is complete and functional.
If using a version of OS X that came on disk, restart from your most recent OS X Install disk, run Disk Utility from that, and check the drive. If that reports problems, see if it can repair them too; that is sadly unlikely if the ‘keys’ remain ‘out of order’. Sometimes this problem can be repaired successfully by Alsoft’s Disk Warrior, or a third-party tool. However such repairs are only really a ‘get you home’ measure to allow you to recover files from the affected disk, and you should still aim to initialise the disk before doing any more serious work on that Mac.
If you are using a version which was downloaded and installed from the Mac App Store, you will need to restart in Recovery mode, from there initialise the drive, and download and install a fresh copy of OS X.
Once your drive has been initialised and OS X is installed, you should be able to restore your apps and docs from your latest Time Machine backup.
The chances are that this error resulted from an earlier crash or forced restart, but that may have been some time ago.
Updated from the original, which was first published in MacUser volume 28 issue 13, 2012.