Being a shared hosting env, and having multiple names on each virtual mailserver (i.e. mail.domain1.com, mail2.domain2.com etc), what would be the solution to stop thunderbird and other clients from complaining about the bad cert that is presented on SSL connections? Shall I give customers a generic fqdn like "secure.myhostingco.com" ?
You should provide your customers a common mail-server name, that has a valid certificate installed, e. g. mx.myserver.com or whatever your mailserver is named to. Otherwise you would need a multi-domain certificate and add each single domain of your customer to it (I don't think you want to spend that much money )