You have hit most of the reasons and background behind certain codes: some are old military installations, or other field names that kept their identifier even after being renamed. Some of them are a byproduct of the naming convention that was instituted a while back:

All naval air stations start with N, therefore certain cities like Nashville, which had an identifier starting with N, needed to drop a letter and add something to the front - therefore BNA. Other cities did the same with adding a B or other generic letter. Some are just creative---such as Key West (EYW). If the airport or station is a weather reporting station a K is added to the front (KIAD, KORD, etc.) therefore Key West now becomes KEYW.

Others that are unique based on location are MBS (Midland-Bay City-Saginaw), IAD (International Airport Dulles - rumor only), and CHO (Charlottesville, VA) couldn't be CHA (Chattanooga).