Just to update, I resolved the issue with the reverse DNS through the Linode manager - to my servers FQDN, so that doesn't come up anymore.
Still the issue persists though.
When I send an email to an address on the server I get a bounce back with the error message:
Diagnostic-Code: X-Postfix; Host or domain name not found. Name service error for name=smtp type=AAAA: Host not found.
Does that ring any bells?