When I had to search for a large e-mail, I went for the try-and-see-if-it-works method, and used the search term size:5000000
to find e-mail of 5MB large, and that seemed to actually find all my emails larger than 5MB. I tried different numbers and it seemed to work consistently.
Even though this operator isn't documented in the advanced search options, it worked for me. :)
As of November, 2012, this is now an officially-supported search operator. The syntax is a little different than it was.
to find emails larger than 5MB, you can search for
size:5m
orlarger:5m