I'm making decently complex system, where many entities are referencing each other, and I don't want to allow any broken references. That is why I would like to implement validation at entity deletion, but where should I actually put it?

I know hook_form_validate runs on deletion, but it is hard to know if it has been invoked by deleting operation. I guess I can also do proper check in access callback of entity, however it isn't about access but validation, and I think that would be ugly workaround, as those are two different things. What would be a good place to put, a validation mechanism for deletion that would query the database to know if deletion of entity is possible?