Algún día, con tiempo y amor, voy a explicar como aprovechar al máximo los beneficios de Gmail y la cantidad de tiempo que pueden ahorrar al centralizar todas sus cuentas en una sola, manteniendo backups automáticos y asegurándose de no perder ningún correo por fallas humanas (No, Google no sufre de esa clase de errores 
).
Gmail tiene un plus que lo hace estar muy por arriba de cualquier otra solución que conozco, su motor de búsqueda. Es simple, rápido y muy preciso, además cuenta con varios operadores destinados a ayudar a los usuarios avanzados (léase rompe-pelotas) a restringir sus búsquedas para encontrar lo que necesitan utilizando extrañas combinaciones matemáticas de origen jedi.
Ok, hasta acá muy lindo, pero hoy la cosa viene mas por el lado del reclamo, estuve media hora tratando de encontrar un correo que estaba convencido había ubicado bajo el label “x”, pero por algún motivo el correo no tenia el label en cuestión, es mas no tenía ningún label asignado.
Entonces se me ocurrió que si puedo hacer una búsqueda del tipo is:unread, tiene que ser posible hacer una búsqueda avanzada de labels usando el mismo principio, por lo que is:unlabeled me tendría que filtrar los resultados solo si el correo econtrado no ha sido asignado a ningún label, pero no funciono porque evidentemente el operador no está implementado.
Revisando la ayuda de Gmail me encontré con que en el detalle del operador label:, hay una aclaración que dice *There isn’t a search operator for unlabeled messages (No existe un operador para los mensajes que no estén asignados a un label o labelados). 
Una lastima que Google no haya pensado en algo que creo es bastante básico a la hora de realizar una búsqueda en 2+ GB de correo, así como tampoco existe un operador is:unstarred.
Marche un feature request …
Mira vos, nunca se me hubiese ocurrido intentar ese tipo de búsqueda, sos rebuscado mierda!
De todas formas me parece util, porque cuando empece a usar gmail no usaba labels y debe haver un gran numero de emails que no estan labelados, ¿se puede votar el pedido en google? ¿hay alguna lista de espera o cola de pedidos?
_labelados_, acaba de nacer una palabra
Con respecto a lo del pedido, no hay una _lista de pedidos_ para votar, pero calculo que mientras mas pedidos haya, mas posibilidades hay de que se implemente
Tengo que reconocer que apenas uso los labels por el simple hecho que bajo todo a mi PC. Le configuré, sin embargo, los filtros para que le apliquen labels automáticamente emulando la división por carpetas que hago en mi PC.
Coincido con Rodrigo en que es algo que puede ser útil para aquellos que hacen un uso exhaustivo de la versión on-line y que nosotros usamos tan poco. De todas formas, el motor de búsqueda de Google es muy poderoso, permitiendo muchas operaciones lógicas. Por ello, se me ocurre que tu “is:unlabeled” puede ser emulado de la siguiente forma:
!(label:label1) && !(label:label2) && ….
Es tedioso si tenés muchas labels; yo probé con un par de labels y parece funcionar. Si lo vas a usar mucho se complica, caso contrario no es tan malo.
PD: Por alguna razón, el equivalente lógico !(label:label1 || label:label2 || …) no funciona
*Mati:* El problema de utilizar los operadores lógicos de esa forma es que sirve solo para excluir uno o dos labels de la búsqueda (muy útil a veces), pero cuando quiero ver *solo* los correos sin _labelar_ (seguimos inventando palabras) y tengo unos 35 para excluir, se me complica un poco. Igualmente no es tan grave, solo que me sorprende que no este contemplado.
P/D: Para usar el operador lógico NOT en gmail, no uses el ! sino el -. Entonces la búsqueda “excluyente”, quedaría así ==
-(label:abc || label:123) search string==.Para la busqueda de is:unstarred podes usar: -label:star