You don't mention much details about your installation, version of mojoportal, Medium Trust? folder or host based sites? related sites mode?
The only situation where I can envision this happenng is in medium trust because you have to specify the index folder in Web.config or user.config like this format:
<add key="Lucene.Net.lockdir" value="D:\__projects\mojoportal\joe\Web\Data\Sites\1\index" />
so in medium trust it may not work correctly as it may use the same index files for all sites. In this case there is nothing I can think of to solve it other than to disable search and remove the search link from the skin. This is only a theory based on your statments.
In full trust I cannot produce this problem on my machine, I have not tried to produce it in medium trust.
In general this should not happen because each site has a separate seach index under /Data/Sites/[SiteID]/index, so I would look into whether files are being written there for all your sites or not.
Hope it helps,
Joe