Today while reading the latest tweets of my VPS provider, I noticed that they had some problems with one of their DNS servers. This led me on a strange train of thought about why the login prompt for my server would take so long to show up when I was using SSH. Could it have been their slow DNS server? Nah, that''d be silly! After a bit more research though, I found a blog post detailing two reasons for SSH slowdown. Turns out the culprit really was the nameserver, so I popped open /etc/resolv.conf and added in the 3 nameservers suggested by Grokthis and now it takes a mere second to show the prompt!

Just goes to show that the impossible is merely improbably.... is likely the case.