What finally worked for me was an if-you-can't-beat-em, join-em approach:
Mis-sorted artist by mis-sorted artist, I manually entered into the "sort artist" field the name I wanted it to sort by. Often this was just a matter of cutting-and-pasting from the "artist" field, but with a large library it still took a while. After several syncs and resets, the fix has held.
I know this is an old post, I've been having the same problems. The artist order on my device gets out of whack whenever I add new artists to iTunes and then sync my device. The artists on device move down the list, and artists on the bottom of the list drop off and disappear. It's like my device can't expand the number of artists available on its own.
I have a found an easy work around for this problem, and it might work for any other similar problems. In iTunes I highlight all of the songs, right click and select Get Info. Select the Options tab, then adjust the Volume Adjustment slider any amount. Click OK to save this setting. Then I sync my device. Everything is back in order and under the right "A - Z" heading, nothing repeated, and nothing missing.
It's not a fix to the problem. I have about 6000 songs in iTunes, My computer was syncing the changes just below 1000 songs / 10 minutes, so it took just over an hour total. There are probably faster ways of accomplishing the same task, but it keeps you from having to uninstall iTunes, or resetting your device...just a few mouse clicks and a little bit of time.