Fundamentally the issue is that you want to preserve the order at the table level (vs. sorting in the grid).
To do that you will have to either keep an order column in your DB or else delete ALL and resave ALL records each time.
I have a few many-many relationships in my app where the ordering matters - I use a Jquery multiselect widget on my create/update form. You could do something similar outside of the gridview as a first step.