@john-2 - we can't add any indexes at all to any of the tables as it's a 3rd-party app that pushes its data through to SQL. The only thing we can (and do) do is bring the statistics up to date every night and do index maintenance at the same time.

I used DBCC FREEPROCCACHE to clear the cache (but I think I might have used the wrong command) but only just before the first run of the second set (if that makes sense).

Even after that, the VS version and executing the proc itself (instead of just the INSERT INTO) was taking over 10 minutes against 30 seconds.

Now everything is back to something resembling normality (without me doing anything else) so I'll have to keep an eye on it.