For XP, about once a year...but I often didn't need to do so. Man, I used that OS on about half a dozen personal machines since it hit the streets (and still use it at work)...and after they got the bugs worked out in the first year, it was the most stable OS that I had ever used. Thus, I was mostly just reformatting to clean things up and satisfy my OCD.
With Win 7, three time thus far.
- installed and it was awesome...but I made the mistake of installing a media meta data synch tool that installed SQL Server without warning...and after extensive effort to remove all traces of it, I finally just reformatted.
- Massive Explorer instability - all related to right-clicking. None of the suggested tweaks solved it...so...
- is a charm so far. Only one right-click explorer crash...and none since uninstalling AVG and moving to MSE.
In general, I keep all data on a separate drive so reformatting is a breeze. In XP, I simply retargeted "My Documents" to a different drive...and I do something similar with Win 7's libraries. I don't ever backup the OS and apps. I like to start clean and reevaluate what I want and get the latest versions each time.