Is it mandated in a reg somewhere that address change requests MUST be in writing from the customer?

See the FACT Act requirements that were implemented by making changes to the FCRA.
Essentially, a request for an address change can be an ID Theft Red Flag & you need to verify that it is really your customer making the request. For a lot of banks, the most practical way is to require a signature for the Add Chg request & verify the sig against your signature card.