I think they'd still have to offer a pro rata refund for the annual fee. You can't just send out an email telling people the product they paid for x months ago just changed and they'l l have to just deal with it.

They did. Emails get lost. Snail mail gets lost. It happens, it sucks but if companies have to refund people every time they don't get the memo about something we're all in for some trouble.

Sounds like a message during checkout (click checkout and instead of confirmation of order get a message explaining the change, and have to click checkout/confirm or something) would be helpful to alleviate this problem.

That would be totally reasonable, and it's something I see all the time. It's usually titled "We recently change how blahed blah works..."