Incremental Backup fails after last incremental backup set was deleted

You can't.  When you do an incremental backup, BE keeps track of the incrementals so that it knows which backup sets to use during a restore.  I am surprised that you are able to delete the incremental.  I guess you manually delete it because BE will not allow you to delete the last recovery point.

First of all Backup Exec permits the deletion of any type of backup set as long as you are aware of the dependancies. That is why you have a red X as a button.

From what I understand, when you delete a backup set (from the storage tab within BE2012) you will delete the entire dependency tree. As I deleted the LAST incremental (from the storage tab within BE2012), there were no warnings, as it was the last one. 

I then reran the incremental backup job which backed up the changes made after the deleted incremental and not after the last incremental or full backup available, thus failing verification.

Even if I would have deleted another incremental it would have deleted the one selected and the others after it which are dependant. So runing an new incremental job after the deletions shouldn't it check the last available incremental or full and continue from there?!

Also the option to perform a full backup if the incremental isn't supported was selected in the backup options.

I then reran the incremental backup job which backed up the changes made after the deletedincremental

This means that your backup chain is broken.  You do not have the changes between the incremental backup done before the deleted incremental backup and the deleted increment backup.  This is why you need to run a full backup before you can continue further.

I assure you I have it because I have verified the last incremental backup by means of BE verification and by means of restoring emails and vmdks from it. 

So to review. I have full backup A, incremental B,C,D. I deleted D and reran an incremental job. The incremental job had transferred less data then D had transferred. Before runing the new incremental I have tested C as mentioned above.

You do not have the changes between the incremental backup done before the deleted incremental backup and the deleted increment backup.

Yes, because I have deleted it. 

Yes, because I have deleted it. 

Precisely, so your backup chain is broken.  There is no point in continuing with the chain.

I think you have no other solution than rerunning the full backup. As you deleted the incremental data, your backup chain is broken. Even when you are still able to run an incremental backup, your data will not be consistent. Consistent = the incremental data is missing.

What I can recommend is change your backupmethod to full and daily differential. A differentials does the same as an incremental without resetting the archive bits or modified dates. You will notice that the monday backup (diff 1) will be significantly smaller than friday (diff 5). The reason is that all data starting from the last full will be on tape or backup set.

The biggest advantage is that you need less media for restoring a server (the full and latest differential).

Using Vlad's definitiomn

If the Full set is A and you have incremental sets B C and D and you delete set D

Then when you run the Incremental that becomes set E the chain will be broken because you only have A B C E and not A B C D E

What is in an incremental job depends on the state of what you are backing up at the time of the backup and not the state of the last set in the chain as such if you delete set D when the next incremental E runs it only goes back to the end of D and it will not include the content of D which will break the sequence. As such if you have deleted the last part of an incremnetal sequence, the next job that you run should be a full in order to maintain a complete valid backup sequence to the last full.

Also we do let you delete the last Incremental set in a sequence, if you tried to delete one of the earlier sets in the sequence it woul pop up to tell you that dependent sets exist.