I think that the filesystem mapping differences might explain it.
If you could try a test with SMB on your Mac instead of AFP it would be interesting.
I did this test this morning. I repeated Test #2 below, but first I unmounted the file share on the Mac, disabled the AFP service on the fileserver (leaving only SMB), remounted the fileshare, and confirmed that it was mounted via SMB.
The results were exactly the same as in Test #2 - anything with an accented character in the Artist, Album or Name is not found, and will not play.
So I started thinking about this. There should be no filesystem mapping difference going on, since the exported library is a .zip file. As far as I know there's no system to system translation that goes on with a binary zip archive. Once the target windows machine unzips it, it should be the same as was created on the Mac.
I unzipped my test library and couldn't figure out which file held the pathnames, so substituted another test: I exported a playlist (from iTunes and also from MC) with just the tracks from the album "Alizée - Mes courants électriques" included.
A sample line for one particular from the MC Mac playlist .xml looks like this:
<Field Name="Filename">/Volumes/public-1/iTunes/iTunes Media/Music/Alizée/Mes courants électriques/11 Cœur déjà pris.mp3</Field>
...but in the playlist exported from iTunes, it looks like this:
<key>Location</key><string>file:///Volumes/public-1/iTunes/iTunes%20Media/Music/Alize%CC%81e/Mes%20courants%20e%CC%81lectriques/11%20C%C5%93ur%20de%CC%81ja%CC%80%20pris.mp3</string>
Ugh. So if the same thing is happening in the exported library, then it's the way the data is being written out.
Let me know if you need a copy of that playlist, or if there's anything I can do to assist. And thanks for your attention to this issue.