Criminal pardons
Saito could have arranged a pardon for Cobb from a state governor. That would permanently solve his legal problems, and the deal could be sealed in just minutes.
In exchange, Saito could have pledged to deliver either new jobs or better energy prices to the state, either of which a state governor would be glad to have, especially if the cost is a pardon for one fugitive with no other criminal history, one whose murder case could be hard to prove at trial.
This is not that far off from how some American defense contractors operate: they make sure to establish offices in every state, so that they can threaten local politicians with layoffs and a local economic downturn unless they get favorable policies.
And who's to say that pardoning Cobb would be an unjust trade, even if he were guilty as sin? Wyoming was the least populous state around the time the movie came out, with about 500k residents -- that's a lot of utility to weigh against one murderer. The Framers of the Constitution famously believed it was better to let one guilty person go free than to wrongly imprison one innocent person, and our legal system was designed with just such a bias.