I found a solution for this Android bug on a Russian-speaking Google Wave devoted to Android! By the way, I encourage everybody to join Google Wave ASAP (no, I already used all my invitations).
A solution, or should I say - a workaround? - is to use Meridian Player http://sites.google.com/site/eternalsandbox/Home instead of Android's own Music Player. Meridian Player allows to forcibly re-scan media files.
As I was told on Meridian's forum, "Yes, it is an Android's media scanner issue, and I also don't know what's the actual behavior of the auto scanning. Before 1.1 it will do a full scan each time replugging SD card, but now it does not. Even manually invoke (by Meridian) sometimes fail...Hope they can fix this soon."
I wonder why Meridian developers know that, while Google Android developers do not.