The mails seem not to be pushed immediately, but only delivered through a rescan (that happens every 15-30 minutes). Detailed explanations and solutions to this problem can be found here:
BlackBerry Slowness in an Exchange Environment | CrackBerry.com