To use, fetch wl-fastfind.el from https://gist.github.com/egh/46c6ced69402a92c0ec6 and evaluate.
There's one bit of the code that I find interesting -- support for native Gmail searches. Perhaps you could create a new kind of search, the Gmail type, and integrate it clearly into WL's search functions? (I'd do it myself, but I don't use Gmail.)
-- Juliusz