Es que, la mejor forma de hacerlo es con una preconsulta para comprobar si hay un registro con esos datos...
No entiendo como te falla una consultade ese tipo, es de las mas básicas. A lo mejor tenias algun error y no lo viste. Esta es la mejor forma de hacerlo:
1- Recuperamos los datos del formulario.
2- Recorremos los checkbox, recogiendo su valor.
3- Consultamos a la BBDD si hay algun registro con ese valor.
3.1- Si lo hay, no hace nada.
3.2- Si no lo hay, que cree uno.
Debes usar
para saber si se ha devuelto algun registro de la BBDD al hacer la consulta del punto 3.
Creo que te estas complicando mucho la vida, con algo que es muy sencillo.