If there is something in the mailbox, calling Delete All Emails soon after Open Mailbox keyword does not seem to do anything (calling Wait For Email after returns me emails straight away). It works though if I Delete All Emails and Close mailbox in the test teardown. I was trying to solve this issue with:
Open Mailbox
Delete All Emails
Close mailbox
Open Mailbox
but it looks the emails are still there :( Is there any lag/cached test data that may cause invalid state?