Since no NDRs received, from the exchange control panel, I traced the message delivery and below was what I saw in the delivery report.
And the mail queue was as below.
It was clear that mails are being queued in the mail server. Next what I did was, I checked the mailbox database drive for the free space. The drive had about ~200MB more free space and the total size of the queue didn’t exceed or wasn’t even near that. But I went ahead and cleaned up the disk and gained more space there. Then all the emails that were stuck in the queue for the particular database started to deliver.
This behavior puzzled me. After a bit of a searching, I found this helpful post and as it explains, the behavior was due to Microsoft Exchange Server 2010 resilience improvements to stop the database from dismounting due to low disk space.