Ilustraciones photoshop y vectoriales

Hola, tengo que hacer un trabajo, una caricatura de un mapa, con los lugares característicos, edificios, personas caricaturizadas, etc. Es un trabajo de grandes dimensiones pero no de mucha complejidad, ya que todo tiene que ser en estilo cartoon. El problema que tengo es que me lo piden vectorizado, me encargaron el dibujo de las caricaturas, el color digital, pero ademas que este vectorizado, y realmente no se como hacerlo. Trate con algunos programas para vectorizar como el corel trace, pero aun con una imagen de mucha calidad, al vectorizar queda bastante mal, por más que lo ajuste a nivel fotográfico, los bordes quedan mal, y el resultado no es el que busco. Me lo piden vectorizado porque así ellos pueden agrandar el tamaño sin perder calidad, pero aun no puedo hacerlo, y me piden el presupuesto incluyendo la vectorización, ya he hecho bastante trabajo, simplemente con el dibujo y el color, pero si pudiera vectorizarlo ellos me pagarían más. Por favor agradecería que me diera una mano con esto. Gracias!