No melhor de meu conhecimento, esta não é uma função atual do Rythmbox. Se reproduzir um arquivo, ele será lembrado onde está, para que você possa usá-lo novamente. Não tenho certeza porque você não quer isso.
A menos que você esteja usando uma mídia removível ou um compartilhamento de rede que nem sempre está presente, você poderá ter arquivos em seu catálogo que não podem ser reproduzidos.
Por que não enviar e-mail para a equipe do desenvolvedor e solicitar essa função? Seja claro porque você acha que seria benéfico para a comunidade, porque você está pedindo a alguém para gastar tempo para codificar esta função, é bom se você tiver uma razão convincente.