Short, a new database table would be an absolute overkill.
I think, what you want to do is pretty much resembling the existing menu_order column in wp_posts. Using post meta is just fine, but add it on the the singular staff member posts from your custom post type. So you will have several custom order metas saved for them. And then retrieve the posts (staff members) with WP_Query on the different pages by category and add a meta_query according to the sort order meta field you want, last but not least order your query after the meta field, which means you will likely orderby you meta_value_num. Pretty much all the information you need you get on the WP_Query codex page.
Very brief outline, I hope it helps anyway, but as you are comfortable with saving the data, this should be enough to get you there.
Update:
As answer to comment.
No time for a complete answer, but some (more) general information that should help you.
Firstly, do not use query_posts see:
- When should you use WP_Query vs query_posts() vs get_posts()?
- When to use WP_query(), query_posts() and pre_get_posts
for the why.
Secondly, independent from how you will retrieve your list, you generally already have the $post_id‘s of the single staff posts available. You pretty much just have to make use of this information to make your update_post_meta call address the single posts, instead of the page. A little bit of code refactoring will be necessary, but it should generally be not overly hard to do.
Thirdly and lastly, there are a couple of good plug-ins available which are enabling post sorting via jQuery sortable and saving the data on per post basis. As mentioned above this mostly concerns the menu_order column, but you definitely should take a look at how they do it, because it will be pretty much the same for you, with the only difference that you are going to save your data to post meta fields. So get some inspiration from how it has already be done.
Again, I hope it helps and good luck achieving what you want.