También tienes la opción de deshabilitar el botón de enviar a menos que seleccionen el checkbox:
Código:
<input type="checkbox" name="condiciones_de_uso" checked onclick="javascript:document.(nombre del form).(nombre del boton de envío).disabled = !this.checked" value="ON">
Esto desactiva el botón de envío si deseleccionan el checkbox.
Por dar alguna idea....