Можно найти только все письма с вложениями через поиск has:attachment.

А вообще вот что дал поиск:

Эффективный поиск в почте Gmail

Поиск в Gmail аналогичен поиску Google, но кроме стандартных возможностей имеет много дополнительных, привязанных к почте. Например, в нем можно искать по вашим меткам (Labels).

Введя label:Photos в строке поиска я смогу получить список всех писем, которые помечены меткой Photos. Это действие аналогично нажатию на метку Photos в левой колонке.

Первый секрет быстрого поиска — нет смысла вводить слово label полностью, можно просто написать — l:Photos.

Кроме выбора самой метки можно сразу же найти письмо, содержащее какой-то текст и помеченное вами определенной меткой — l:Passwords site.com (попытка найти потерянный пароль для site.com).

Дальше — больше. В Gmail есть также специальные метки, которые помогают искать письма в вашем Inbox (l:inbox); письма, помеченные звездочкой (l:star); черновики, неоконченные письма (l:draft); отправленные вами (l:sent) и, наконец, поиск по всей почте (l:all), включая корзину (l:trash) и спам (l:spam).

Поиск по всей почте может пригодиться, когда некто должен прислать вам письмо, а вы боитесь, что оно могло попасть в spam, но искать его среди мусора в spam и кучи непрочитанной почты в inbox не хочется (а вдруг еще и фильтр какой сработал). Решение — l:all from:mrgluek@gmail.com

Метки можно комбинировать, например, чтобы найти дискуссии, имеющие непрочитанные вами ответы — l:unread l:sent. Или отправленные вами письма с вложениями (на случай, если вы захотите почистить свой ящик) — l:sent has:attachment.

И напоследок l:voicemail — поиск сообщений голосовой почты, отправленных вам через GTalk.

Удачного поиска!