Anecdote: I have a dirt cheap almost abandoned shared hosting account that I haven't run any live sites on for about 1.5 months. I keep it around for demos, ...etc. I just checked, and they are on MySQL 4.1.21. So, it means even the small hosters have moved (or are moving) to 4.1.