la deducción no es solo para guarderías públicas, si no de guarderías autorizadas por la Comunidad Autónoma, y pueden ser perfectamente privadas (por ejemplo, yo tengo una cerca de casa, pequeñita, privada, y tiene en el cartel de la puerta su número de autorización de la comunidad Autónoma de Madrid).
Por ejemplo, en Madrid hay un buscador que te lista todos los centros de una localidad, y puedes ver si una determinada guardería/centro infantil está autorizado:
http://www.madrid.org/wpad_pub/run/j/MostrarConsultaGeneral.icm
Cada Comunidad debería tener un listado similar.
Por otro lado, no creo que sea legal el hecho de que si a una guardería se le ha pasado enviar la declaración informativa, la madre vaya a quedarse sin deducción, eso no lo dice la ley.
Será más largo el procedimiento, porque una vez que incluyas la deducción en la declaración es previsible que Hacienda quiera comprobar contigo y/o con la guardería la información, si no cuadra, pero al final tendrán que darte la deducción.