GEMS outputs its ballot image using whatever printer settings it is given, so this should be possible. Just set the paper setting to 8.5/11 and tweak the print offsets -- much like printing BOD to the 5si.
One question I have though is how do they deal with the cut marks? Typically print shops print on paper larger than 8.5/11 and then cut to size using these marks. If they are printing directly to 8.5/11 stock then make sure they are aware of our registration tolerances.
They should also be able to do it with any DTP software that can manipulate postscript or pdf. Adobe Illustrator could probably do it, as might Ghostview like Greg suggests. A capable and competent print shop would know better than I which tools are best.