The MP4 limitation applies mostly to mobile phones, not the XBox - it's different. Your assumption about slow transcoding is most probably right - that CPU is not enough to transcode high-def in real time. WMV encoding is one of the slowest one due to the fact that it's single-threaded (because of an FFmpeg limitation), so it will benefit from pure Ghz more than from the number of core (but a dual-core CPU is the recommended minimum for any transcoding).

To skip through a file, it has to be fully transcoded - was the file still being transcoded when you tried to FF?