Yes this is possible. It should be fairly simple - although I'm saying that without looking at the available plugin hooks :)

Having said that, instead of managing the deletions during a build, would it not be best to delete the category directories when you delete a category?

If you want to delete individual pages that become redundant then that is a whole lot trickier and it is going to be tough to locate which links are on which pages and then to figure out which pages are redundant.

Edit:

How about this - a seperate script that you would execute after a full build that would analyze the last modified time for the category pages and delete ones that haven't updated - meaning that they are redundant?