Replace them when you starting coming out of them when you don't mean to, or when the bearings start making noise. They don't last forever. Neither do the cleats.
My experience has been different. I found that cheaper clone pedals wore out quickly, but the actual Shimano models seemed to last almost forever.
I have some of the very first SPD pedals that were used for lots of muddy mountain bike riding/racing, some general around town usage, and quite a few tours including a couple coast to coast ones over the last 35 years or so. I am not sure how many miles are on them, but between two pairs of the original SPDs it must be well over 100,000 miles on the higher mileage of the two and just a bit less on the other pair.
Both have been repacked only once as best I can remember. The exposed parts were cleaned and lightly lubed often. The repacking is a real pain on the ones I have so thankfully it needs to be done very infrequently.
I also have a newer model from 2010 that have less mileage on them but they too are holding up fine. They have required no maintenance other than the normal cleaning and lubing.
If they start to get loose it has generally been the cleats which do wear out after a while, but I have adjusted the release tension a few times (I like them fairly tight).
I am not sure if it makes any difference, but all of real shimano pedals were the simple ones with no platform or cage.
The clones I have handled were widely variable in quality. One set I bought from nashbar for a family member were worthless right from the start with poor quality bearings that were not smooth no matter what I did and release mechanisms that didn't retain the cleats well. Others were OK but wore out much faster than the real Shimano ones. A pair of Performance house brand (Forte campus pedals probably made by wellgo) on my daughter's bike were starting to show some wear after doing one TA tour, but were still in use for a couple years of commuting.
I will mention one other thing. I think it is very important to take the time to get the angle of the cleats just right for you. This usually requires fitting them, riding a short distance, tweaking the setting, and trying them again. Repeat until you are well satisfied with the adjustment. If you don't get it right knee pain can result so take your time setting them up the first time.