Hola,
Tienes que aclarar una cosa: promocion no es solo posicionamiento en buscadores. El posicionamiento solo es una parte de la promocion.
Sobre el posicionamiento, pide un informe de las actuaciones que van a realizar. Hay empresas que en su pagina web explican que van a usar texto oculto y doorways. Visita
http://www.google.es/intl/es/webmasters/guidelines.html y mira lo que dice google sobre esas tecnicas.
Luego hay otras empresas que no posicionan tu web, sino que crean un subdominio en un dominio suyo, y promocionan ese subdominio para esa palabra clave. Y ese subdominio el que sale en los primeros puestos. Cuando acaba tu contrato y no renuevas, ese subdominio esta disponible para que metan el contenido de otra empresa.
Y por supuesto que hay gato encerrado con lo que prometen. Para un termino con 2000 resultados no deberia ser dificil sacar un top10.
Lo mejor es que preguntes a alguien de confianza sobre lo que ofrecen algunas empresas. Por ejemplo, si tienes confianza en la empresa que te diseña la web, podrias consultarles. Porque ademas puede que haya que modificar la pagina web para meter los cambios propuestos por la empresa optimizadora.
Por cierto, ademas del posicionamiento, en varios buscadores tambien tienes anuncios de pago (google y overture-yahoo). Si pagas 1200 euros/año por optimizar en google, con ese dinero podrias pagar 1200 x 0.05 = 600000 clicks/año en adwords de google. ¿Te imaginas que solo obtienes 200000 por la optimizacion? Son cosas que debes valorar.
Saludos.