It seems that, although the message gets accepted instantly, the mail doesn't actually get sent until much later (minutes later). I run qmail at home and, although you may not have this problem, I have had this kind of problem in the past at home. The problem was due to the "trigger" named pipe not getting created correctly. I guess qmail-send listens to that named pipe and, if it fails to do that, qmail-send will only send a message when it wakes up (every few minutes). Anyway, again, this may not be your problem, but you might wanna double-check.