Они просто не реализовали поиск на сервере -- обещали где-то в 2012 году, когда сделали IMAP (как и поддержку пуш-почты по стандарту).
Ну а теперь, видимо, просто не является приоритетом (ни то, ни другое), зачем, когда есть свои приложения, аж целых два.
Сравнивать универсальную программу с "родными" -- бессмысленно. "Родные" скорее всего вообще не через IMAP работают.
В общем, так бывает -- "друзьям -- все, остальным -- хрен с маслом".
