Temporary lookup failure - Postfix kan ikke finde domænet?

Hej folkens.

Jeg har en mailserver med postfix, og fungerer fint med mine egen domæne (har efterhånden en del), men et nyt domæne fucker bare op. Det er oprettet i postfix, og DNS og MX recors er sat op præcis som alle mine andre domæner. Men når jeg prøver at sende en mail, får jeg denne tilbage:

Postfix SMTP server: errors from pqueueb.post.tele.dk[193.162.153.10]

Transcript of session follows.

Out: 220 easy-web.dk ESMTP Postfix (Debian/GNU)
In:  EHLO pqueueb.post.tele.dk
Out: 250-easy-web.dk
Out: 250-PIPELINING
Out: 250-SIZE 10240000
Out: 250-ETRN
Out: 250-STARTTLS
Out: 250-AUTH LOGIN PLAIN
Out: 250-AUTH=LOGIN PLAIN
Out: 250 8BITMIME
In:  MAIL FROM:<ch@easy-web.dk> SIZE=894
Out: 250 Ok
In:  RCPT TO:<test@iicona.com>
Out: 451 <test@iicona.com>: Temporary lookup failure
In:  DATA
Out: 554 Error: no valid recipients
In:  RSET
Out: 250 Ok
In:  QUIT
Out: 221 Bye

Er der nogle med kendskab til postfix, der evt. kan sige mig hvor problemet ligger?