si están en móvil los pierdes. Si están en gmail y los has borrado se puede deshacer desde google contacts
https://www.google.com/contacts a un momento en concreto.
Si estan en la SIM no se hubieran borrado con un formateo de flash.
Lo más seguro es lo que dice yocasta, los tendrías en la memoria del teléfono.