Creo que si alguien te elimina, te aparece el signo de interrogación (el mismo que aparece cuando agregas un contacto y antes de que éste te agregue a ti). De todas maneras, también existen las autorizaciones, que es lo que permite ver el estado de una persona en skype; es decir, que puede que no te hayan borrado pero sí bloqueado o desautorizado.
Existen páginas en donde supuestamente te dicen si el usuario por el que preguntas está o no conectado. Te los dejo por si te interesa:
Amiblocked
http://www.amiblocked.com/
Status Scanner
http://www.statusscanner.co.uk/
Evidentemente, la mejor manera es preguntárselo a dicha persona. Y como último recurso, crear otra cuenta de skype y añadirlo a tus contactos o llamarlo.