I replace the media in each filter once a month, rotating so that I am not doing all at once. My HOB filter cartrides get rinsed every week during water changes. I do a total rebuild of my HOB's about once every 3 months.
Each month I clean and recharge the Nitra-zorb on my Rena XP-3. The foams last for at least 9 months or so. I most likely am replacing media and foams more than I need to, but my tanks are crystal clear all the time. Only problem I ever have is keeping my Nitrates below 40 ppm. I do a 25%+ water change once a week, and I sometimes think the only problem is that the test kits start to give a false reading after a while.
Chris