The Undelete through Cache Recovery utility uses two major cache sources for its working. The first one is the Google cache of course and the second one is the Internet Archive (The Wayback Machine). The latter is totally useless for relatively newer sites, which most blogs are, and therefore Google dominates in the utility usage.
A better cache than Google
Believe it or not, another search engine has a much superior cache than Google. It is the third one of the Big Three search engines, and that is MSN Search.
I know that it sounds controversial and indeed, counter-intuitive; after all, Google is the best search engine out there and has been so for some time. I do agree with that fact, Google is indeed the best right now. But I say this on my experience that I have in using the cache of both Google and MSN and also from some bloggers who had contacted me to help them out in recovering their deleted blogs.
Almost every blog worth its name is well indexed by MSN Search and you can recover the latest post from it within hours from posting it. The more popular your blog, the faster it caches. However, in spite of having a better index than Google, MSN falls behind in searching through them and that is why they are at a distant no. 3.
However, there remains a technical issue in adding MSN to the utility and I have sought advice from MSN in this regard. Hopefully, it will be resolved soon and you can have a better chance of recovering your deleted blogs using the undelete utility.