I have not implemented a Google Sitemap. I was going to a year ago but after reading negative postings I decided not to. Instead and have "pages of links" with custom written anchor text on SEO URLs. I make sure the anchor text and KWs in URL are not identical. I also follow Google's guidelines of "100 or less" links per page and consequently have 7 sitemap pages.
I just noticed that more than half my sitemap pages have gone supplemental (and SERPS are affected) and in knee-jerk fashion have created one large (650+ links) sitemap page and have modified my robots.txt to Disallow sitemap pages 2-7 (that no longer exist). I do things sometimes because my gut tells me too even though I have no research to back it up.
I can change the sort order of my sitemap links (using several variables i.e. not just ascending/ descending) but have not adjusted that yet. I'm wondering if I should.
Are there any opinions out there on the best way to deal with my supplemental sitemap situation and what is the best course of action?
Just because you discovered the problem via the sitemap does not mean that it has anything to do with causing the problem.
In fact, that is very, very unlikely.
You need to investigate ALL the possible causes of supplementals, before taking action.
I'd start with your navigation (arising out of your comments); xenu is your friend.