This is a sure-fire way for the game to work again.
1. Download the installer from taleworlds. You are not stealing, as you are the owner of a CD key. Don't worry, you ain't going to hell.
2. This is important: Do not overwrite the steam directory.
3. It didn't ask me for my CD key, probably because its already in my registry. However, if it does ask you, to the M&B:Warband section of your Steam library. You will see on the right a button for your CD key.
4. Install cRPG into your new installation of M&B:Warband.
5. Use the exe file from your new installation, not the Steam shortcut.