Any kind of sorting gives duplicate results in Views (Search API)
Bleh what a horrible bug. 

I solved it by re-creating the search index (and therefore the view as well).

Why did it happen?

I think it's possible to have certain things saved into the Search Index (possibly when it's created?) and then it's impossible to remove them without just starting afresh.

I discovered this bug while trying to debug this. 

After re-creating the new index the only difference I can find between it and the original is that I can now sort by an un-related taxonomy field (see the bug). Presumably this is an indicator of something as it doesn't seem relevant, but I have no idea what.

Second EDIT:

Actually just re-creating the index wasn't enough to solve this problem, I then continued to find duplicates after. 

Deleting and re-creating the field with a new ID however did work. I never worked out why, but I'm presuming something was corrupted.