Some (relatively few, actually) surge protectors are fail-safe and will stop working if they need to be replaced (e.g. one type of APC DSL surge protector). Others are not necessarily fail-safe but can be checked if they've failed (e.g. gas discharge) and the tubes can be replaced without replacing the whole unit.
MOV-based surge protectors (the most common) are neither fail-safe not properly testable (or are they?) and should probably be replaced on some schedule. However, the schedule will depend on your location (e.g. rural should expect more failures than urban) and other factors. It's like insurance - you pay what you think it's worth to protect the other stuff. If you're paranoid, replace frequently; if your brave (e.g. dumb) never replace and assume everything is fine.
MOV-based surge 'protectors' are barely able to protect the connected equipment even after a few weeks of use if the grid power isn't very clean. MOVs namely degrade whenever there's even a small surge they have to deal with and can be rendered useless quite rapidly.
For a proper surge protector, however, it should be replaced when it tells you to