If we receive a CD interest check back due to a bad address and we have exhausted all our ways to try and locate the customer, in order to prevent any more being returned, can we deposit the check back into the certificate and change the interest dispositon to "add to balance"?

Not unless your contract allows for a change in terms in these circumstances.