A contract re-do usually involves giving the player more upfront/guaranteed money. That's usually a good thing so most say yes.
As for getting him for just $3M, let's assume he gets a 7-year deal with a $20M bonus. That would make the amortized signing bonus $2.86M a year and in the first year players usually get the veteran minimum, so you figure he'd need about $3.5M in cap room for the first year. That's a little over the $3M I mentioned, but if they really wanted him, opening-up another $500K probably wouldn't be a huge problem. But Bailey signed a deal that paid him in 3-$6M installments that were guaranteed, but didn't hit the cap all at once.
There are ways around it is basically what I'm saying.