The underscore in this domain key is a challenge for my entire customer base. I am with a reseller hosting business and have been for years with a lot of clients set up. Upon trouble shooting with them the error message in creating a TXT DNS DMK record we found the issue is they can't seem to make the underscore pass validation.
This will only be resolved with a conversation from Campaign Monitor to my hosting supplier to talk them into it. Until then, anyone with a gmail address is not getting the e-news.
The underscore is part of the domainkey specification and something that's required (read more about that here). If they aren't able to add the key in via the panel perhaps they could add it in via the back end or something along those lines? There isn't a way around having that underscore in the key.