Сталкивался с таким. Из-за этого, в свое время - были вынуждены отказаться от использования Gmail в корпоративной переписки, так как менеджеры писали сообщения с предложениями клиентам (потенциальным), клиенты писем не видели (из-за попадания в папку Спам) - продажа срывалась.
Копались в чем причина, что только не делали, в итоге позвонили в гугл, описали ситуацию. Тех.поддержка нам сказал в чем проблема: гугл помещает в папку Спам, письма которые приходят с IP адреса не соответствующего с IP адресом сайта. Точно не помню, но нам даже сказали как решить эту проблему, но только для писем приходящим к нам, что на с не устроило, так как у клиенты то таких танцев с бубном не делали.