Query very different speeds on seemingly similar data

I've got a weird problem that I can't work out...
A customer was complaining that their system was running slowly. They've only been using it for a few days, so we tested it on our copy of their data and it's running at normal speed.
Uploaded our backup to the live server and it's still quick.
Restored a new backup of their live database on our local test server and it's REALLY slow. So the problem seems to be data-related.
I've run Analyse, Vacuum and Reindex and still no change.
I've stripped the query down to the bare minimum that causes the speed difference.
The only difference between the "good" data and the "bad" data involved in this query is about 80 extra records in an invoice table (which had 250,000 records to start with).

It's behaving (in my opinion) like it does if Analyse isn't run after restoring data, or as if the indexes are broken. Explain Analyse shows it is running the query in completely different ways on the two databases.

The query, now I've stripped it down to the offending part, is as follows:
SELECT stk_key,
(SELECT SUM(stdp_quantity) FROM sales_invoicedetails_purchlinks
LEFT JOIN sales_invoicedetails ON std_unique = stdp_std_unique
WHERE stdp_loc_key = '__NBI' AND std_stk_key = stock.stk_key
) as level
FROM stock

Table "stock" has about 5000 records, sales_invoicedetails has about 250,000, sales_invoicedetails_purchlinks has about 80

The bit that kills it is the "std_stk_key=stock_stk_key" in the sub-query.

On the "good" data it runs in less than 100 milliseconds, on the "bad" data it takes ten minutes!

Explain files attached (assuming attachments will get through to the group - otherwise what's the best way to post it?)

I'm completely stumped - any suggestions most welcome!

Med vänlig hälsning / Best Regards

Rob Northcott
Software Developer (UK Office, formerly TEAM Systems)

Phone +44 1752 712052

Compilator AB
Södergatan 22
SE-211 34 Malmö
Sweden
www.compilator.com<http://www.compilator.com/>

[Asset 2(at)2x]<http://www.compilator.com/>

THIS COMMUNICATION MAY CONTAIN CONFIDENTIAL AND/OR OTHERWISE PROPRIETARY MATERIAL AND IS THUS FOR USE ONLY BY THE INTENDED RECIPIENT. IF YOU RECEIVED THIS IN ERROR, PLEASE CONTACT THE SENDER AND DELETE THE E-MAIL AND ITS ATTACHMENTS FROM ALL COMPUTERS.