Before Jedi I thought Fett would work for anyone if the price was right (something that Kenner played on when introducing the action figure to the ranks of their plastic people collection).

It would have been much more interesting seeing him working with the Rebels and getting them the Death Star location information instead of the unseen Bothan spies, that would have created a bit of tension between Leia, Han, Lando and whoever hired him which would have added a bit of depth to story.

But doing that would take a huge amount of work if it was even remotely possible.

I'd much prefer to see a more dignified death for the guy than have him removed entirely.