I encountered the same issue when reconstructing land cover from 1988 in Tanzania. I looked for old Land Cover maps of national parks, aerial photographs and reports and used them to check with the corresponding land cover reconstruction map. Ideally, your validation is random so you'll never manage to validate it to the same extent as your recent maps.
you can perform the same image classification using different satellite data which will help you to cross validate your results.
However, the best option is to visually compare your results with High resolution image from Google earth (with same date). For this you can generate random points , overlay them on google earth imagery and add class as per you requirement. This is very lengthy but will will help you. Hossain Mohammad Arifeen