Ahhhh, yes there is a way!
Go into the selections list for your backup job, and within the View format section on the top right of the jobs properties windows select 'Text'. You'll then see a text version of your complete selection list, which should include those servers which have been removed. Simply select the offending entries and delete them.
The graphical display is always based on the current network setup, which is why you had the problems, but the text version displays what you ACTUALLY have in the selections list, regardless of network / server status.
Keith