Finally resolved this issue after a whole weekend (and the rest!) of headbanging!!!
Turns out the HubTransport component was stuck in the draining state.
Blockquote get-servercomponentstate -identity SERVERNAME
Blockquote set-ServerComponentState -Identity SERVERNAME -requester maintenance -Component HubTransport -state active
Restarted the Exchange Transport Service and bingo! emails started flowing. YAY!!!!
Kudos to the guys on this thread: https://www.reddit.com/r/exchangeserver/comments/4emwku/hubtransport_component_stuck_in_draining_state/