Não faz mal, vamos esperar então até que o Rhythmbox implemente esse recurso.
O Banshee já faz isso. Li uma vez na net que tem um patch (não sei onde) para que o Banshee também encode antes de passar a música (se vc tentar passar um ogg para o mp3 player e este não toca ogg o banshee já encoraria para mp3).
Se esse suposto patch entrar na versão oficial vai ficar muito bom.