Thanks for the suggestions.

The data in the affected database is different to the unaffected databases.  I've tried dropping and recreating the indexes and running update statistics against the related tables...