I did it! I added a blank host header entry to the OWA Virtual Directory. Previously there was one entry that required connections to come from the external URL "mailgate.blah.tld"
What I think is happening is that the SUBSCRIBE command is a new connection that is established from the Front-end server to the back-end server on behalf of the client. Because I only had a single entry on the VDir that expected the source to come from the public URL the SUBSCRIBE command was failing (501 not implemented) The blank host header allowed the front end server to establish a connection and thus allowed the SUBSCRIBE command to succeed.
Push now works!
Thanks for all help/assistance.
Hope this might help others to. Please read all comments by me to get a full picture of the problem I was having.