[MrEyes]

Rightio, I have rebuilt the searchindexes using the command line utility as this is a mid to large site and doing this via ACP isn't really viable.

Unfortunately this made no difference, the problem still remains.

Regarding the suggestion of clearing the search log. Are you talking about done a delete from / truncate of the searchlog table? Fairly simple to do via SQL admin but thought it better to check before I wade in with a delete command

For reference, here is the output from the reindex:

[root@s17738471 temp]# php searchindex.php
PHP Warning: PHP Startup: apc.shm_size now uses M/G suffixes, please update your ini files in Unknown on line 0
Please enter the path to your vBulletin directory: /var/www/vhosts/mysite.co.uk/httpdocs/
Rebuild Search Index
--------------------
Note:
You should not normally need to empty the search index, however if items are showing in search results after they have been permanently deleted then emptying the index and rebuilding the search index will fix this. Search will not work correctly after emptying the index until the index is fully rebuilt.
Click Here to empty the search index.
Empty Index [0/1,Default=0]:

0) All
3) Forums
1) Posts
7) Groups
5) Group Messages
11) Visitor Messages
16) Blog Comments
15) Blog Entries
Content type to index [Default=0]: 0
Turn off DB indexes during rebuild [0/1,Default=0]: 0
Item id to start at [Default=0]:
Number of items to process per batch [Default=10000]:

Building Search Index Forums ...
IDs 0-140 ... Done (0.22 sec)
Building Search Index Forums: Done
Building Search Index Posts ...
IDs 0-10000 ... Done (26.08 sec)
IDs 10000-20000 ... Done (26.84 sec)
IDs 20000-30000 ... Done (25.90 sec)
<snip>

My SSH connection timed out at around 140k, so after logon I restarted the index at 140k - the only difference was that I set the rerun to use 1000 batches rather than 10000 as this made progress more obvious. The following is the last few lines of the output

IDs 2346000-2347000 ... Done (4.88 sec)
IDs 2347000-2348000 ... Done (2.38 sec)
IDs 2348000-2348538 ... Done (1.53 sec)
Building Search Index Posts: Done
Building Search Index Groups ...
Building Search Index Groups: Done
Building Search Index Group Messages ...
Building Search Index Group Messages: Done
Building Search Index Visitor Messages ...
Building Search Index Visitor Messages: Done
Building Search Index Blog Comments ...
Building Search Index Blog Comments: Done
Building Search Index Blog Entries ...
Building Search Index Blog Entries: Done
Building Search Index: 0 hours, 59 minutes and 00 seconds