In addition to selling purchase history, CC companies may also be (at least partially) funding the rewards with transaction fees.

Some cards (e.g. Amazon Store Card) get you relatively high rewards at a specific vendor (Amazon). I predict there are special deals in place with the banks/transaction processors involved that make these rewards more possible.