Emails deleted remotely in Zoho Mail through IMAP (e.g. on your phone) may not be immediately deleted in Mailbird, even after the folder is refreshed.
Please see the 'IMAP Expunge Options' paragraph here for a resolution:
http://www.zoho.com/mail/help/imap-access.html#alink3