While I was writing a utility last night to accomplish roughly the same thing, I ran into this neat little trick with Explorer that I never knew about:
http://www.addictivetips.com/windows-ti ... -and-size/
Granted, even with the Windows indexing service it's still painfully slow--and slower still if you have the service disabled like I do (~15 minutes to search for files over 100 megs on 460ish gigs of data)--but it's a handy tip if you haven't seen it before.