> lossless MPEG

I don't thinkt this exists. MPEG (and especially MPEG-1 which is used for VCD) is by definition a lossy compression algorithm. I don't know premiere to well but maybe you can improve quality by inserting more key frames ( this will ofcourse produce bigger files). A former customer of mine did some VCD's I'll ask him which settings he's using (although he doesn't use premiere but Ulead Media Studio afaik).