You can't get back a deleted record unless you do revert to the most recent backup that was created before you deleted the profile. This of course may undo other things because the backup resets CRM to that point in time.
Setting up a new profile is not hard and should take few minutes if you have the proper role. What you need to do after that which will take sometime is to fix all mailboxes to point them to the new profile and enable them again.
