Who is your mail host and is this for all messages or just those from a specific group of people? It's possible that the delay is coming from your host and not the device. Also, what is the behavior if you go through your host's webmail (if it's offered) or use a desktop mail app?