If I back up my gmail account then delete some emails, then back it up again (choosing "new messages only"), when I restore it will the deleted emails come back?

Also, I just spent a few days cleaning out my inbox, and deleted about 1200 emails and changed the labels all around (I'm a little messy), is it OK to just update the backup with "new messages only" or is it safer to back up the whole thing again from scratch?

Thanks!