Respondendo a minha própria pergunta, recebi meus sons de notificação de volta, mas não sei por que eles pararam em primeiro lugar.
O sistema dá a você a escolha entre diferentes backends phonon - gstreamer, vlc, xine e assim por diante. Uma página que encontrei ao pesquisar, mencionou casualmente que o gstreamer não funcionava, mas o vlc fez. Bem, no meu caso, eu só tinha a opção de vlc, mas instalei o gstreamer como um teste (então eu teria a escolha), e esse funcionava.
Então, agora, tecnicamente, tudo está bem. Mas eu ainda estou preso com a pergunta por que o backend vlc, que foi o único instalado depois de tudo, só parou de funcionar depois de anos de bom desempenho. E somente para as notificações; os tocadores de música que fazem uso do mesmo backend ainda funcionavam normalmente. Se alguém puder me esclarecer, ficarei encantado. (Muito upvoting e aceitando seguirão.)