wp_delete_post() always triggers before_delete_post – the problem must be that you’re hooking your function conditionally (i.e. not all the time).
before_delete_post only gets triggered if you’re actually deleting the post permanently, not just trashing it.
If you need to listen for trashing too, use wp_trash_post.