Lunar soil or lunar regolith, is mostly created by meteorite and micrometeorite impacts which directly pulverize the rock, or from the ejecta from the impact. Some amount (I can't seem to find any figures) is also created from high-energy particles in solar wind causing bits of rock to spall.
In theory, the bootprints would last until the soil turns over from the space-debris impacts, or the ground shifts due to an moonquake or thermal expansion.
According to this paper, there is a 99% probability that the upper 0.5mm will be turned over 100 times in $10^6$ years. That works out to about once every ten thousand years for the top 0.5mm of the soil. It goes on to say that for a depth of 10cm (probably slightly deeper than the bootprint depth) you'd have to wait on the order of $10^9$ years to see it turn over. However, this is if you worry solely about impacts. Let's move on to moonquakes.
The Wikipedia entry on moonquakes suggest that there are four different kinds of moonquake. Deep moonquake, occurring ~700km below the surface. Probably nothing to worry about there. Meteorite impacts, which as we just saw are pretty rare. I'd say the chances of an impactor large enough to destroy a bootprint probably around 5-10cm deep, are very low. Thermal moonquakes, and shallow moonquakes. Of the four, probably the second two are the most likely to cause damage to the bootprint.
Thermal moonquakes are caused by the temperature shift between the day side of the moon, and the night side of the moon. With an almost nonexistent atmosphere, the temperature differences would be huge. However, according to these sources, (1)(2) thermal moonquakes are very mild, and therefore would probably not threaten the bootprints. Maybe some of the soil around the edges would fall in, but nothing major.
That leaves shallow moonquakes. Recorded to be as powerful as a 5.5 on the richter scale, if moonquakes threaten the prints, this type would the kind to watch for. However, I can't seem to find any studies on regolith turnover caused by quakes. Wikipedia suggests that an earthquake of a 4.5 or higher on the richter scale can damage buildings, but I doubt that even a 5.5 moonquake would do very much to the bootprints. I would lean toward what I said regarding thermal quakes and say the edges might fall in, but probably no major damage.
I would say that depending on the distance from the lander, the most damage to the bootprints probably came when the upper section of the LEM blasted back into orbit. If the prints were close, the exhaust almost certainly stirred up dust which would settle in the print. Or, if the print was directly next to lander it may have been filled in or otherwise destroyed much the same way an outflow from an shop-vacuum can stir up dust.
Ultimately though, given the number of marks they made, if you include the buggy tire marks and other bootprints, the chances that there will be evidence that those men walked on another world will, assuming they don't get disturbed by another mission/collectors, almost certainly exist for at least several millennium.
Moonquake and lunar regolith turnover. (Google scholar search)
Regolith shifting from thermal effects.
as to convection cells and gravitational forces, I didn't see those on the search either. It's worth a little more poking around though. I'll add any info I find as I find it. :)