It turns out I was mistaken. This bug does still affect Rhythmbox and I just wasn't doing it right. The 'Remove' feature works as advertised if the file is not in the folder designated as the music library in the Rhythmbox preferences (~/Music by default). If the file is in there and the user attempts to remove it from the database, it is reloaded the next time the library is scanned.
It turns out I was mistaken. This bug does still affect Rhythmbox and I just wasn't doing it right. The 'Remove' feature works as advertised if the file is not in the folder designated as the music library in the Rhythmbox preferences (~/Music by default). If the file is in there and the user attempts to remove it from the database, it is reloaded the next time the library is scanned.