Note: This answer has changed as of July 23, 2014. Because of the April 11, 2014 external MDM failure and some additional corrections and improvements, both the data and analysis portions of this answer have changed, so read carefully. If you are interested in the previous versions of this answer, please view the edit history.
How often are they replaced?




Sources: [2001], [2007], [2014]
In previous analysis (see edit history), I erroneously included an MDM replacement on a Space Shuttle in 2008 as part of the ISS MDM replacements. I also skimmed over the 2007 replacement and did not realize that it involved replacing not one but three MDMs. The MDMs (best described in this infosheet from Honeywell) are divided into three tiers. There are three Tier 1 MDMs responsible for Command and Control. One is primary, and the other two are backups. There are six categories of Tier 2 MDMs which relay commands to various systems. Two MDMs exist for each category--one primary, one backup. Finally, there are three categories of Tier 3 MDMs which execute commands from the Tier 2 MDMs. In the Internal Systems category are 11. Twelve are Power Systems MDMs, and 8 are External Systems MDMs. In all, that's 46 MDMs.
It is notable that in the first decade of the life of the ISS three backup Tier 1 MDMs have had to be replaced, and one primary Tier 1 MDM had to be replaced at the same time as the backups.
Can we confidently say that the reliability of MDMs is increasing, that is, can we disentangle the effects of solar cycles from changes in manufacturing quality?



[Source of NOAA Charts]
Since we only have three data points, there is a high margin of error for extrapolating from them. We can see that the first replacement coincided with a crest in solar activity, and the next three coincided with a trough, though there were momentary spikes in magnetic activity that may have coincided with the MDM failure. The most recent MDM failure did coincide with a crest in activity, but unlike the previous failures this was an external MDM and not one of the Tier 1 MDMs.
From this it is difficult to derive a correlation between the solar cycle and the need to replace MDMs. However, it is notable that both solar activity crests in the lifetime of the ISS coincided with MDM failures! We cannot say with any confidence that the reliability of MDMs is increasing. It seems that a few MDMs need to be replaced every 6 years or so. The Command and Control MDMs seem especially vulnerable, which is a serious issue.
What are the lessons from the ISS avionics experience for our future missions beyond LEO?
Only five of the 46 MDMs have had to be replaced during the life of the ISS. A few do seem to need to be replaced every six years or so, so it may be necessary to take this into account for future missions beyond LEO. However, since we have little data on the effect of the solar cycle on MDMs, it is difficult to tell what effect increased radiation beyond LEO will have on MDMs. It may be that increased radiation results in a greater frequency of computer failure.
The vulnerability of the Tier 1 MDMs is particularly troublesome if solar activity is connected to the failure, because the more extreme environment beyond LEO may make this untenable with the current technology. On the other hand, there hasn't been another Tier 1 failure since 2007, so perhaps the issue has already been handled.