While my MediaServer implementation is still in it's very infancy, I was already asked by more than two people if it will work with Xbox. I didn't have a clue since I don't have an Xbox so I asked Naba if i can visit him on some weekend to find some clues but he was kind enough to lend it for a week instead. For the past one week I had been having lots of fun with it. This nice page by Frank Scholz gave me headstart and I was able to get Xbox see my MediaServer rather sooner. The only other achievement I had in the whole week is that Xbox is able to see the videos but can't play it (most probably because I don't give it all the metadata it requests).
The good thing is that now i have a very good idea of what Xbox expects from my MediaServer and I am very hopeful on getting my MediaServer working with Xbox at some point. Here is the log of all the SOAP messages I get from Xbox for anyone interested.