Comment 8 for bug 655831

@Tormond: Actually the indexer (IMO) should work as a background job using CPU (limited) when idle. Instead it takes control of the system regardless of what is running. It causes issues with other applications, creates a possible hardware issue, etc. I do however agree with your last comment that it doesn't belong on the desktop unless re-engineered.

I suspect that the above is why there were changes made in the Maverick release:

apt-xapian-index (0.39ubuntu1) maverick; urgency=low

  * debian/postinst:
    - when upgrading, ensure the index is fully rebuild (in the
      background) to ensure that we get updated information in
      /var/lib/apt-xapian-index/{index.values} and that the index
      fully utilizes the new plugins (LP: #646018)

I guess the question is how to test in lucid. I've just installed that version <https://launchpad.net/ubuntu/+archive/primary/+files/apt-xapian-index_0.39ubuntu1_all.deb> & will give it a few days to determine if it helps.