I think the problem is with the Search feature (which has been dodgy ever since the forum upgrade). I wonder whether there is a 'reindex' or 'rebuild indexes' option available from the admin control panel (I am only familiar with phpBB, not vBulletin).