Search all archived mails in the server in Apple Mail for OSX Mavericks
I can confirm that the IOS 8 Mail app (and on IOS 7) searches all IMAP mailboxes on all 5 of my mail accounts on different servers when I use the search box via the "All Mailboxes" list item in IOS Mail. It can take a little while sometimes but it always works for me. 

In Mavericks Mac Mail I leave the Inbox selected when I search otherwise it seems to search only the selected mailbox.  

In the case of Gmail Archived mail it must depend upon how Google has implemented their Archive mailbox. But if it is a regular IMAP mailbox, your search will include its contents.