I just tried foobar2000. It doesn't seem to work. It appears that the %album artist% tag doesn't work here. In most, if not all cases, it's not picking up the data that I had set in MediaMonkey.
If foobar2000 finds a custom tag which can not map to its predefined set of fields, it usually shows it up with <NAME OF THE TAG> in the Properties window. foobar sometimes fails to read all tags (for example, if they use an unsupported codepage), but I don't think MediaMonkey does this. So, to use such custom tag, you have to enclose its literal name in %%
I also suspect that it didn't find all of my songs, but I can't see any way to verify this -- there's no report I can find that would give me even a total count of them.
Drop the directory that contains all songs in a playlist, go to View -> Playlist Switcher and voilà. Alternatively, if you're using the media library, activate the album list, right click on "All music" and then select "Properties".
I haven't tried mp3tag yet; from the website I can't see how my task could be accomplished.
Again, you have to drop the files in the file view, and go to Convert -> Tag - Filename, and play with the tags there. To create folders in such dialog, you have to use something like %name of one tag%\%name of another tag% IIRC, the syntax is pretty similar to foobar.