They could sign their messages? Also needs users to have easy to use mua that handles signing and shows "this is genuinely from your ISP unless they/you've been hacked".

For critical service info I'd want SMS personally, from a verified number with a link on the company main domain to verify the info.