Where do you actually get these error messages? The additional parameters you pass to mail() just get passed on to the mail server you are using, and so the results will depend on what server you're using to send email. Are you using sendmail?
SMTP is a protocol that inherently expects that delivery could take a while. Some mail servers even arbitrarily reject the first attempt to send a mail, forcing the sender to retry again later, just to discourage lazy spammers.
It may be the case that when your mail server can't connect to "gmail.dk," it assume there is only a transient connection problem and intends to try again in a few hours (or even in a few days). It could be that some of the other addresses you tried to send to replied with a more specific error (like, "that user doesn't exist in our system"), allowing your server to know the delivery failure is a permanent one.