Simple, efficient, and effective.
I wanted to do what I consider complex sorting. For my test, on a fresh installation of WordPress with the Twenty Eleven theme, I created 3 posts and 2 categories. I placed all 3 of the posts in both of the categories. I then sorted the posts in each of the categories in different orders, and Custom Category Post order gave me the category independent sorts without a hitch (Just make sure you have the "Use Ordering for selected Category:" check box checked.)
What really impressed me was the ease of re-sorting. When you drag the posts to different orders you do not see anything happen on the page; there is no sign of anything refreshing, but indeed, no sooner are the posts reordered in the plugin interface, they are reordered on the front-end.
It simply works. Thank you, faaiq and Sr. (Or is that just one person?)
P.S. My Post Order looked like it had some promise, but I was able to reorder everything with Custom Category Post order more quickly than I could even set up My Post Order to even begin sorting, and then it didn't work at all. (I appreciate the effort and generosity of developing these plugins; no disrespect intended)