What is MAD version 1, 2, and 3?
MAD version 1 and 2 are used with MIFARE Classic cards. MAD version 1 uses sector 0 of the card to assign the remaining sectors (sectors 1..15) to specific "applications" (each sector can be assigned to one application ID indicating the application that manages/uses those sectors). MAD version 2 is an extension of MAD v1 that is used with MIFARE Classic 4K cards. MAD version two uses sector 16 as an additional directory to assign the 4K-specific sectors (sector 17..39) to applications.
MAD version 3 is used with MIFARE DESFire (EV1) cards. Since you specifically asked for MIFARE Classic 1K, this is probably off-topic for your question.
Who manages the initial MAD directory on a given card?
Typically, the MAD would be managed by the card issuer. Thus, whoever issues the card would also initiate the MAD sector(s).
What is the standard if a card is read which the MAD has yet been placed on the card?
If you happen to find a card that already contains data but does not use the MAD, you would typically consider this a single-application card. Since the applications that already use this card would probably not understand the MAD concept, you would not be able to introduce a MAD later on. (That's particularly the case if the application uses any of the MAD sectors (sector 0 or 16) for other application data.)
Would it be appropriate to write my own MAD to the card in this case?
See above. Usually it would not make sense to introduce a MAD later on. Also, if the card already is in use, you would probably not have the keys to write to the MAD sectors (or any of the other (used) sectors).
Or is it more appropriate to force clients to purchase cards with MAD preinstalled?
I'm not aware of any directory manager service where you could purchase empty cards with a pre-configured MAD and where users would be able to get their specific applications installed onto the cards later on by that manager.
In fact, the MAD is usually used in closed-loop application scenarios where one card issuer uses the cards for multiple applications within their domain (e.g. a university (right, I'm working for one) that uses these cards for an access control system, for a closed-loop payment system, etc.)
Given a standard MIFARE Classic 1k card there are only two 16 byte blocks of sector 0 which the MAD directory may reside. This provides only 32 bytes for the MAD directory. The list of registered AIDs seems to be much larger than the 32 bytes.
In MAD v1 and V2, each AID has 16 bits (2 bytes). Since the MAD assigned sectors to applications, each sector has a two byte slot within the MAD where the AID that a sector is assigned to will be stored. See How to access a MIFARE Classic card that uses the MIFARE Application Directory structure?.
What process should I take if the AID I am looking for is not indexed in the MAD?
You could request NXP to register your application(s) and assign AIDs to them. See the appendix of the application note for the MIFARE Application Directory for the registration form. While the list suggests that NXP is still taking new registrations, you should keep in mind though that MIFARE Classic security is broken since 2008 and there are newer products in the MIFARE product line that would be more suitable for new applications.
Given a specific AID what the general process for identifying which sector the data resides?
See above and How to access a MIFARE Classic card that uses the MIFARE Application Directory structure?. Each slot in the MAD assigns an AID to one specific sector. Thus, you would read the MAD sectors and then browse them for the occurence of the AID, by accumulating all occurences you get a list of all sectors assigned to that application.
