Exchange routing groups. Several international offices but 1 routing group but no VPN between all sites

Hi Experts,
We have 5 exchange servers which are all in the same exchange organisation. The servers are in Milan, Barcelona, Paris, London UK, Poland. We only have 1 routing group in the organisation. In the routing group we have 1 internet mail connector and we have set the option of "forward all email throught this connector to the following smart host" and this is set to "cluster3out.eu.messagelabs.com". in the internet mail connector in Local Bridgeheads we have all 5 servers listed. However we don't have a full meshed VPN so when a user from Poland emails uk it sits in the exchange queue and doesn't know how to route. I think the best way is for each site to send email out over the internet and have a routing group at each site which sends out via messagelabs. Am I guessing right and if so ho do I do this? I would want each site to send out directly to the internet through messagelabs.

If i'm going about this the wrong way please can someone tell me what I should be doing. Thanks
I have attached a pic off the setup
routing.jpg