Personally I use Sorenson Squeeze or Compressor 2 depending if I'm on PC or Mac. If you have the full commercial release of Xpress Pro then it should have come with a copy of Squeeze, so that might be a good place to start.
Try exporting as a quicktime using the "animation" codec in avid. I use settings millions of colors+ at best quality and keyframe depending on my frame rate. Be sure to click off the avid codec and use custom settings. I usually export my movies in there *native dimensions* but use 720x480 *Size to Fit* for Width and Height just to be safe.
The Squeeze that came with my Avid was severely limited, so I use CinemaCraft Encoder Basic on QT Ref files exported out of Avid. It runs about $58. I do 2-pass VBR encodes and have had great results.