If this is the case, how feasible is it to adopt a new domain name? I understand that this may not be desirable, but given what appears to have been a maligned history, it may be the most prudent course of action to ensure that your new product does not suffer from guilt-by-association.

That'd be a last resort if we can't get it somehow whitelisted. But since the product isn't live, it is technically still possible.

Huh? Then how do you know other security products haven't blocked it? I'd say change it if it has bad records. And I'd do some research to see what that Domain used for before.