This does not seem like it would be difficult to add to the HRPERSNL file. Yes, it would require 3rd party applications to update as well. This is not uncommon and with enough advance notice could be accomplished easily. This has been requested by clients for a number of years.
I would rather see former last name rather than maiden name. It does not matter to us if the person changed their name due to marriage or not. We just need to know that they had a different last name. In addition, we have a need to search by the former last name. We often know our employees by last name. We cannot find them if they changed their last name, and we do not know the current last name. This is also an issue when trying to verify employment of a previous employee.