Yo tengo un Galaxy S de Movistar y otro de Orange. NINGUNO de los dos venía libre (y lo puedo asegurar al 100%, sin lugar a dudas de ningún tipo). Eso sí, liberé los dos antes de meter Froyo, porque ya leí que daba problemas.
De todos modos, la herramienta (Samsung Galaxy S Unlock Tool) tiene una nueva versión (2.0). Prueba con esa a ver si te funciona y te da los códigos. Yo lo hice con la antigua y con los teléfonos con Eclair. No sé ésta nueva qué tal irá.