I can't speak as to other types, but my experience is paste wax will stay good for at least 4 or 5 years. I've never kept a can longer than that, to find out if it will last longer.
The only time I had a can of paste wax go bad, is when I left an applicator in the can with the wax. The applicator had been moistened with water to help the The wax spread easier. It took a couple years, but the wax started smelling mildew like. Perhaps it could have still been used, but I threw it out.