Thanks for the insight here.

I did actually go ahead and index the table on DELETED() to see if there were performance benefits, and boy were there? an increase in speed of around 80% was achieved.

The reason was that most of the queries were pulling in around 10-25 records from this particular table, and around 175-200 of the records not obtained, were deleted. So I do have a happy customer @ the moment.

Thanks for the comments etc.
Kev