On Linode, were you using the default single IPv6 address, or did you request a prefix? I found that the default address was in a blacklisted /64, and couldn't send email without it getting bounced or blackholed. Once I got my own /64, the problems went away (but DKIM+SPF was also mandatory).