Problemas con el servidor???

[ChristianDavid]

Buenas tardes, espero que me puedan colaborar a solucionar este problema que tengo, les pido que no se maneje un lenguaje vulgar si les parece absurda mi duda, Gracias por respestar eso.

Actualmente tengo un vps, en la empresa donde trabajo se encargan de hacer envio masivo de mensajes solicitados para los boletines, las personas que administran el vps nos permiten hacer el envio y no hay ningun problema ya que son mails solicitados, antes de eso estabamos en otro hosting por hay enviabamos los mensajes y llegaban a bandejas de entrada de hotmail y de yahoo, pero ahora que hicemos el traspaso al vps tenemos problemas ya que tanto hotmail como yahoo nos mandan para la parte de correo no solicitado, ya mire la direccion ip a ver si aparece en listas de correo negras y no aparece dicha direccion ip en listas negras, lo mas caso del asunto es que desde que se hizo el traspaso todo esta fallando y los administradores del servidor dicen que eso no es problema de ellos, aparte hay mensajes que supuestamente salen del servidor de entrega pero nunca llegan, aproveche que tengo otro espacio de la misma empresa que nos da hospedaje y use esa cuenta para enviarme un mensaje a hotmail y a yahoo y para sorpresa tambien los halo para correo no deseado, aun no se a que conclusion llegar ya que todo aparentemente esta limpio, podria alguien decirme que podria suceder en este caso, Muchisimas Gracias por sus respuestas