Have you looked at the Email logs to compare when the instance receives the email with when the case is created?
To do that, go to the sys_email table and filter by Type is "received" AND Subject is "<whatever the email subject was>".
I ask because there is time between when someone clicks send from their mailbox, to when the mailbox actually sends it off, then the internet does its thing, the instance receives it and processes it to create the case. I have never heard of an instance receiving an email and taking that long to process the email so I would think it is something before the email reaches the instance.
