De acordo com a sugestão de Jimmy, o comando do Windows dir permite uma saída mais bonita, o que me deu o melhor resultado:
dir *.mp3 /s /w /b > lostFiles.txt
Claro, remover * .mp3 de lá dá todos os arquivos, mas nesse caso eu só precisava de música.
O comando Reference to dir está aqui: link