they have to pay out his contract
Not base salaries. In a contract there is basically guaranteed and non-guaranteed money. They non-guaranteed comes in the form of base salary and when a player is released, then that money is forgotten about. It isnt held against the teams cap and they dont have to pay the player this portion.
Now, guaranteed money comes usually in the form of a signing bonus. Signing bonus is amortized over the length of the contract. In other words, if a player gets a $10M signing bonus on a 5 year deal, the player is payed the full 10M up front, but the the cap hit of the 10M is spread out over the 5 years of the deal. So the cap hit from the guaranteed money will be $2M/year. This helps the team cap wise and when you see news that a veteran "restructured" their deal to help the team, all it means is that the player converted some of his base salary for that year into bonus money, which the team to spread out over the length of the players deal. Its a win/win. The player gets a guaranteed payment, the team saves cap room in the short term.
Now, heres how it works as far as the player being cut. Lets say a player signed a 4 year deal worth $12M, with 4M of that as signing bonus. So we have $8M in base salary charged over 4 years, which is $2M a year. The 4M in bonus is spread over the the length of the deal, so thats another 1M per year in bonus money. After the 3rd year of this deal, the team decides they want to cut the player. When he is cut, the team saves the 2M base salary they owed the player. But the 1M in amortized bonus is charged to the cap, so in reality they only save $1M. All signing bonus money left on the contact when a player is cut is charged to the cap, even though the money has already been payed to the play when he signed, because the team spread out the cap hit.
This is why some bad players arent cut or traded. Say a players base salary is 1M, but he has 4M in bonus money still spread out over his remaining contract. If he is cut or traded, the team will save his 1M base salary, but will be charged 4M against the cap. So they really lose 3M in cap space. The Dolphins could find themselves in a similar situation if Jake Long blows.
OK...this was my longest post ever. I hope its understandable because I feel like im just rambling on and on. Also not that this only applies to SIGNING bonuses. Roster bonuses are charged to the cap they the year they are recieved and are not amortized.