Shoutbox

The 'Remove Ads' option was removed as Messenger has ads to make money, just like Plus! has the sponsor package to make money. However, you can use a plugin like StuffPlug-NG, or a patch like Mess Patch.
Replacing the 'Add Contact' button - not sure what can do this.
There are numerous plugins for other media players. A quick search will reveal some for Winamp at least.
TabServ is already serviced by a patch.

Besides, Patchou won't do any patching, as it's against the Messenger EULA.