So Windows Vista Media center gives you a “Cannot Play Video, One or more codecs required to play to open this content could not be found”.
Are you running the 64bit version of mediacenter? Follow these steps to get it working:

1) Download and install the approperiate decoder, my favorite is ffdshow. You’ll need the 64bit version: http://sourceforge.net/project/showfiles.php?group_id=173941&package_id=229162&release_id=559173
2) Change Media center so it uses the 64bit version of media player instead of the 32bit one
– Open the registry using regedit
– Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\
CurrentVersion\AppPaths\wmplayer.exe
– Remove the ‘x86’ items and make sure afterwards it looks like this: 

(Default) – “%ProgramFiles%\Windows Media Player\wmplayer.exe”
Path – %ProgramFiles%\Windows Media Player

3) Close regedit
4) Open a command prompt and type this: %windir%\system32\unregmp2.exe /SwapTo:64
5) Reboot the media center box
6) Leave a reply if it worked 😉

Now your good to go, Media Center will play your Divx and Xvid!

UPDATE: Somehow it doesn´t work at everyones Mediacenter, please have a look at the comment by FINN, it might help you!