Oliver Sommer 
2009-01-08
Because of Exchange 2007 syncronisation cycles of 4 (four) hours from the Hub transport to the Edge role it may take up to 4 hours to publish a new email address to the public faceing Edge server to accept mail directed to that email adresses.
A Microsoft KB Article also discribes that by design behavior:
A newly created recipient may not receive e-mail messages for up to 4 hours