I'm guessing you would need to watch the Encoding profile to be one of the mobile device compatible category, but you'd also need a decent player which support the MP4 files and has a good h264 decoder.
Here is a quote from an article about the video capabilities of the G1
It turns out that the G1’s
capabilities are pretty similar to
later generation iPods, iPhones and
Zunes. H.264 video on the G1 needs to
conform to the Baseline Profile and
the 3.0 Level, which govern some of
the impermissible encoding options
like CABAC and B-Slices, that are
powerful options but also drastically
increase the complexity of the file
and the power needed to decode the
video content. Maybe even more
crucially, G1 video has to be follow
very strict resolution limits, as no
video can be wider than 480 pixels
across and no higher than 368 pixels.
Bitrate does not appear to be nearly
as strict. I’ve gotten the G1 to play
files with surprisingly high bitrates,
up to 2000 kbps, but that is generally
way overkill for files with sub-SD
The same guy wrote a nice MeGUI encoding profile and a guide Video encoding for the Android: Step-by-Step, it doesn't use Adobe Media Encoder, but MeGUI which is a very nicely build wrapper around a lot of great powerful command-line encoding utilities.