I just did a test message (PC to Wii) and it took one minute for it to show up. During this time, my Wii was idle on the message board screen. Keep in mind that the Wii has to periodically check Nintendo's servers for new messages. The system will not receive a message until the next time it checks the server (every x minutes).
Edit: Wii to PC is taking quite some time (for both of my e-mail addresses). I suspect that Nintendo is having trouble with the servers that handle outgoing mail (e.g., SMTP).