Long delay when sending mail

[chny]

So I've been using this installation of the toaster for a good few months now, been working perfectly.

Now all of a sudden (really, i didnt do anything with it, this is a dedicated box) sending mail takes quite a while.

telnet to mymailserverhost.tld 25 yields a very long delay until it responds.
That tells me it's having some problems with DNS or PTR's or something like that but I'm unable to a) understand why that would happen all of a sudden and b) find anything in any logs about this (feel free to tell me other places to look for this).

The box also resolvs the domains in question (source hosts) perfectly fine from shell, both PTR's and DNS.

Any ideas what has happened here and how I can fix it?

I don't have the money it'd take to get someone pro to actually look at this seeing as this is a private mail server but it's quite important for me, my girlfriend and a few bum-poor student friends in need for for an email server

Any suggestions would be very welcome.