If you try the same address on our online demo at http://www.cfdev.com/email/verify/example.cfm you'll see it usually takes about 3 seconds to return the results of 4 tests.
A typical mx lookup takes about 500ms.
I've recently seen denial of service attacks generated by anti-spam tools on dns servers, servers with network connection problems that went unnoticed (working on cache with occasional connections) and of course sobig.F and mblast traffic have plagued many dns servers with unusual traffic.
Temporarily switching dns servers will usually reveal the problem.