He eliminado algunas canciones que solía escuchar mi compañero de cuarto, pero siguen reproduciéndose cuando activo la reproducción de música en iOS 7. No puedo entender cómo sucedería eso. Una canción se encenderá. Iré a mi única lista de reproducción. No estará allí, pero sigue jugando. La próxima semana lo mismo. No tiene sentido. ¡Ayúdame a odiar su música!
Las listas de reproducción son solo subconjuntos organizados de tu biblioteca de música, por lo que es posible que no tengas la canción en la lista de reproducción, pero que aún la tengas en la colección. Incluso si solo tienes una lista de reproducción, eso no significa que cada canción de tu teléfono esté en ella. iTunes irá por defecto a la primera canción alfabéticamente si le dices "Reproducir" cuando no tiene una lista de reproducción cargada (es decir, la primera vez después de encender el teléfono).
Al menos en iOS 6 (no he actualizado aún), puedes ver todas canciones tocando la pestaña "Canciones" en la parte inferior de la aplicación Música. Si su música está ahí, puedes borrarla desde allí. Si no es así, entonces hay algo más en juego.