Turns out this is a bug in jabberd2. What my server sends to Google is <presence.xmlns=‘jabber:client’.from=‘email@example.com’ to=‘firstname.lastname@example.org’ 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 email@example.com and any @gmail.com Jabber user. Sweet.