Alex, how does your search on Mailroom compare to Remail? I loved Remail's wicked fast search on my iphone.
One of the issues that I've had personally is that I can't search across multiple inboxes. Maybe using some of Remail's guts we can figure out how to make that work.
the entire feature process is similar to mailplane though: we look at mobile gmail and say "how could we take whats already there and make it beter" or "what's missing and how can we add it"?
Big upcoming features include things like HTML email reading and the ability to add attachments, both major features missing from Gmail Mobile.