What works

Installation of Primary Game

Loading the game (with No-CD patch 1.3 and d3dx9)

Campaign mode

Battle mode

Historial Battle

Tutorial

What does not
Nothing

What was not tested
Multiplayer
Kingdoms Expansion Pack

Additional Comments

I did the install through PlayOnLinux UI, but I believe the results would be the same directly through Wine.  Detailed install steps:

1) Within PlayOnLinux UI, I selected to do manual install for since there is not a script for it.  I installed it into its own prefix (i.e. namespace).

2) Was prompted that Gecko is not installed, so followed instructions here to manually copy it in - http://wiki.winehq.org/Gecko

3) During install, there is a checkbox on the Additional setup options page to "Install or update DirectX".  I unselected that based on this FAQ: http://wiki.winehq.org/FAQ#head-fbaa851e07d7484640cc10b6d0c48abc741260b2

4) I did not install the Kingdoms games because I had a problem swapping CDs.

5) After install, I used winetricks to install "d3dx9" dlls per instructions on the main "Retail CD 1.x" page - http://appdb.winehq.org/objectManager.php?sClass=version&iId=6517.

6) Replaced medieval2.exe with a no-cd version of 1.3.  This worked fine even the "HOW TO" section on the above-mentioned page says you should use 1.0.

I have played about 20 hours of a campaign and one Historical Battle sequence without any problems.