Wow este si es un caso raro, en primer lugar uno no puede registrar un dominio que expiro dentro de un plazo de X días (no recuerdo ahora) porque son los días que el actual dueño tiene para renovar.
Si tu lograste registrar el dominio es por que ya paso todo ese tiempo y quedo libre nuevamente, ahora si tu proveedor te dice eso es seguramente una jugada que quiere hacerte para darle preferencia al anterior dueño del dominio de que sea suyo nuevamente (en el caso que también sea cliente de tu proveedor), si no es cliente de tu proveedor a lo mejor tu proveedor quiere quedarse con el dominio. Huele sospechoso.
Pero en general si tu pudiste registrar el dominio sin problema, es por que ya quedo libre, tu proveedor solo puede mover el dominio nuevamente registrado al anterior dueño, porque los que se encargan de registrar y todo eso son de ICCAN. Entonces seguramente tu proveedor te dijo eso para que sueltes el dominio y se lo pasen al otro tipo.
Y con lo que dices de que figuran tus dns, con eso compruebas que el dominio es tuyo, así que no te dejes engañar, el dominio es tuyo.