Somewhere around 1998 or 1999 the US government agreed to allow US airlines to pay the overflight fees to save time/money on the flights. Prior to that carriers did, in fact, have to fly around Cuban airspace.