Turns out this is a bug in jabberd2. What my server sends to Google is <presence.xmlns=‘jabber:client’.from=‘firstname.lastname@example.org’ to=‘email@example.com’ type=‘subscribe’/>. Note that the XML namespace is set to jabber:client despite the fact that this is a server-to-server connection. D’oh!
In any case, Google have added an interop work-around and I can now communicate between firstname.lastname@example.org and any @gmail.com Jabber user. Sweet.