Sony Ericsson's non-smart phones (e.g. K800) had OTA software updates. They would pop up a dialog from time to remind you to check for updates, then download them and update, all on the phone. (Carriers would often hold them back, though, if you had a carrier-customized model.)

I'm pretty sure I got an actual update at least once.