A family of Microsoft relational database management systems designed for ease of use.
Sounds like you got to the correct solution. I have, however, seen this symptom in databases that had become corrupt; sometimes the key icon would be restored by manually resetting the field to be the PK - and later disappear again.
It would be prudent to compact and repair, if you haven't; or (perhaps better) create a new, empty database and Import everything from this.
Is the database properly split (and all this is happening in the backend)? If not - run, do not walk, to the database splitter wizard or otherwise split it! A shared database is at real risk for corruption.