BIMI + VMC seems like an expensive workaround, we'll first experiment with your first two recommendations. We'll also have to figure out a way to reset the score with Gmail. Hopefully they haven't penalized the whole domain, and a new from-address will do it.

Thanks again for taking the time out to share your thoughts, really appreciate it! :)