I restored my mail server. Now I see messages/mailboxes that were deleted?

mailbfr does an incremental backup by default. So unless you change the backup location regularly you may end up with old messages. This is by design otherwise you couldn’t go back to an old messsage a user might request. If you do not wish this behavior, use the "full" or "rotate" option.