We have received consistent feedback from our customers that the ability to reject messages for invalid recipients at the service network perimeter is important. We are aggressively working to design a solution that will make Directory Based Edge Blocking (DBEB) available within Exchange Online Protection (EOP). This functionality is targeted to be added to the service in the first quarter of 2014.
In the meantime, here are some suggested configurations to help customers who want this type of capability until the service is able to offer recipient validation:
Wendy Wilkes Senior Program Manager Office 365 Customer Experience
Updated 11/21/2013 to include the target release timeframe.