I had this idea, when a follower such as ED-E disappears you really can't get him back outside the PC, and perhaps patching the game so it doesn't happen would be to difficult, but here's an idea for a simple fix.

Add a method to dismiss a follower WITHOUT talking to them. In fallout 3 you could get lost followers back by traveling to point lookout or the pitt as those DLC's would automatically fire your followers and return them strait to their home. If say you could fire a follower by talking to his replacement after the companion declines it gives the option to fire the old follower. Or maybe using the terminal in the Lucky 38 Suite, it could solve the problem in most cases, and would likely be infinitely easier then preventing it from happening at all.

I hold no illusions of a patch actually being made to implement what I think is an easy solution to a troublesome problem, but if I didn't voice my idea it have no chance of being done, and maybe offering a possible solution instead of complaining might help.