Given that what you did was a reindex, what probably happened was it used an index scan to try to locate the toasted values in the table and couldntcouldn't find one. This sounds like a corrupted index. Vacuum analyse does alter the table but reindex does not and the changes are very minor.
The way to think about this is that TOASTed attributes are actually broken into chunks of about 4k in size and these are stored in rows. They are looked up and sorted/reconnected with the main row at query time. It sounds like an index used here was corrupted and so the reindex solved the problem.
I have found corrupted indexes are usually a sign that something is not well with the server. It is good to check and make sure memory, CPU'sCPUs and hard drives are all happy and not reporting problems. I have found overheating servers to be particularly prone to index corruption and if indexes can get corrupt one has to worry about data becoming corrupt too.