Just incase the admin doesn't already know ... PMs seem to get sent, but you're presented with a PHP error page after clicking the send button. Happened to me twice around 15:45 today.
Nope, they are instant. What do you mean by take 20 mins to send though, are you talking about the notification, as there really is nothing being "sent" as such, it's just an update in the database, just the same as a forum post?
Chris, you're referring to them staying in your outbox for ages? They are sent instantly, but appear to remain in your outbox until the recipient has read them - which allows you to see if they've been received.