Have a query that runs in 01:58 and returns 517860 records. Rewrite it a bit for performance reasons, try running again, now it runs in 01:17 and returns 517870 records. Where the hell did I pick up those extra 10 records on that many total records?
I hate optimization...

New records created while you were rewriting the query?

@Fiftyseven great idea, thanks! But no, no one other than me has access and I haven't been inserting.
I've compared the results ans it seems that the 10 records were oroginally filtered out somewhere (they are "weird"), but I'm not yet sure where as there's no additional inner joins or changes to where conditions...

Switching from an Inner/Natural join to a Left/Right can add lines with null values.
Group by or "having" conditions can have influences too.

Lads, thank you but I was not really looking for an answer to what could have gone wrong. I know what can cause different results, this was a rant, not a question. Thank you all, but I've got it :)