Your beef isn't really an issue with the 360 codecs or the players, as the title suggests, but rather the server app. running on Windows; its a Windows thing, not a 360 thing and it has to be solved on the windows side.
XBOX media streaming is done via an implementation of UPnP/AV, not file system mounting (as you do when sharing files across PCs). Strictly speaking, the 360 doesn't see PCs on your network and they don't see your PC file systems at all. What they see is directory structures offered up by UPnP/AV server apps. (They don't have to be PCs; NASes will do if you find one thatvsupports UPnP/AV in a 360-friendly way. I think LaCie used to make one.)
WHS has a built-in UPnP server app that runs as a service (built off the old Windows Media Connect) while WMP has a newer one and Zune the newest of them all. That is the 360 sees. If it doesn't see a file that it can play, its the server app's fault.
Alternatives exist.
Two you may want to look at are:
1- Tversity (which has built-in, on the fly transcoding for support for well, non-supported files):
TVersity - Home
How To: Stream Any Video to Your Xbox 360, Playstation 3, and Nintendo Wii | Maximum PC
2- Playon (which captures net content into UPnP playlist-like structures bringing stuff like Hulu, youtube, and CBS.COM into the 360):
PlayOn! | MediaMall Technologies
Linux users can use, as you mentioned, Twonky,
TwonkyVision
and Mac users, Connect 360:
Nullriver Software : Products : Connect360
As well as Twonky.
Basically, the issue is not with the 360 (the dashboard client plays what it can see) but with the Windows server apps that don't necessarilly show the stuff properly.
Want to try a simple test?
Take some of you h.264 files and burn then to a data dvd or copy them to a thumbdrive or external usb hard drive.
Betcha they play...
...as long as they follow the rules:
Xbox Team : December 2007 Video Playback FAQ
Of course, with Windows 7 Media Center bringing in h.264 support, the 360 won't be limited to just UPnP streaming. And then, there's no telling how the new architecture behind NXE coming on nov 19 will affect media playback over the next year or so...