Eu também tive esse problema.
Quando eu sair do Skype no Ubuntu, ainda recebo notificações. Eu decidi desinstalar o programa.
Depois de executar sudo apt-get purge --auto-remove skype:i386 , descobri que ainda podia receber notificações.
Eu corri ps aux | grep skype para ver quais processos em execução eu ainda tinha. E eu vi um processo em execução. Eu matei esse processo com kill process# e reiniciei e não vi nenhuma notificação.