Фильтры, предписывающие письмо отметить звездочкой (да и все пользовательские, вроде бы), срабатывают раньше GA спам фильтра: если по «вашим» ключевым словам письмо получило звездочку, а потом спам фильтр засунул его в спам, то в спаме оно будет все равно со звездочкой.
Так что:
1. Делаем такой фильтр с «вашими» словами и фразами
2. Запоминаем в левом меню поиск «in:spam is:starred»
И по мере сил вспоминаем об этом всём, просматриваем сообщения и жмем на действительно не спамных сообщениях «не спам». И да, он вполне себе обучается — года четыре это использую.