You have the same problem with DirectX games (althoughTransgaming has more or less solved this one), and with Windows Media Player.
I actually checked that 2 minutes ago when I read your mail. I called a friend of mine (who owes me some favours) to check the WIndows media issue.. (I asked him that 2 days ago)
He checked it a bit and it seems that there are few holes in this license agreement, so you have 2 options:
1. You can put Windows media player for free download with a note that a user needs to have MS Windows, but *it doesn't have to be installed* on the machine. This solution could cover 99% of potential Wine users (or CrossOver plugin users/clients) since almost all the workstations machines are being sold with Windows.
2. A second solution is to give it to an IP lawyer who can dig the holes quite quickly and can give you a statement if you could just put it for download without any notes for end-users.
I hardly think that MS will do any problem to CodeWeavers if you guys decide to support it. After all - for them it's just means more clients are using WMP to watch video/listen to audio and a better selling point of their servers..