Unrecognized database format error occurs when attempting to view a Personal Geodatabase

Error Message

The following error occurs when attempting to view a Personal Geodatabase in ArcCatalog, or when attempting to Add Data in ArcMap."Failed to connect to database.
An underlying error occurred.
Unrecognized database format 'C:\Test.mdb'."

Cause

The geodatabase has become corrupt or has been modified in another application, for example, with a text editor.

This error can be reproduced by opening the .mdb file in Notepad, deleting a few lines, saving the database, and then trying to view the database in ArcGIS.

Solution or Workaround