Issue resolved.
It took several mail server outages to resolve the issue.
The delay is caused due to the unread table corruption on the mail file. Marking all mail as READ in the mail file and doing offline nFIXUP, nUPDALL and nCOMPACT -c resolved the issue.
RIM is working on an optional QuickFix (to be released in future) which will disable the unread marks feature for the affected user. (Basically all mail will be delivered as READ until the mail file maintenance is done.