Hola ANGD!!
Cuando borras una cuenta de correo del iPhone, y estabas sincronizando los contactos de esa cuenta con el iPhone, se borran también los contactos. Para volver a verlos en el iPhone debes volver a configurar esa cuenta de correo, o guardar los contactos en iCloud. Para ello, abre esa cuenta de correo en Safari y ve a la sección de contactos. En el iPhone, verifica que tienes iCloud como cuenta por defecto para guardar nuevos contactos. Lo podrás ver desde los Ajustes del iPhone, Contactos, Cuenta por omisión. Después, abre la app Contactos o ve a la pestaña Contactos de la app Teléfono. Desde ahí, crea un nuevo contacto. Alternando Safari y la app Contactos podrás ir creando nuevos contactos con los datos que tengas en la cuenta de correo y ya se irán guardando en iCloud.
Con respecto a que el iPhone te dice "Puede ser [número telefonico]", es posible que sea por que el iPhone recuerda que ese contacto estuvo guardado en él, por medio de los archivos temporales que se crean con el tiempo y el uso. Pero claro, ahora ya no está ese contacto, por que al borrar la cuenta del iPhone se borraron también los contactos del iPhone.
Ya nos contarás que tal te ha ido.
Saludos!!