Could it be caused by something else than the 3.0 upgrade? I just can't see how something like that would get into Relevanssi index, especially if you delete old revisions. 3.0 has new indexing process, but it's copied from Relevanssi Premium, where it has worked for a long time without problems - so the code should be ok.
So, I'm thinking there's something else going on. Especially if reindexing doesn't help. Any plugins that could cause problems?
Anyway, here are instructions on how to debug Relevanssi indexing issues. You might want to check them out, in case the problem is in indexing (if it's not, then we can debug searching). http://www.relevanssi.com/knowledge-base/how-to-debug-indexing-problems/