I don't play video games so I can't help you. Hopefully someone knows the answer.
I've had no problem with my videos converted using the AppleTV preset on both my AppleTV and my 360. If you're using a Mac you're going to need Connect 360 to be able to stream to your xbox (unless something has changed in the past little while that I don't know about).
xbox 360 is compatible with mpeg4 H.264