I was going to use Views until I realized the limitation. What you are seeing for the taxonomy pages is custom sql I wrote for the purpose that makes use of the arguments passed by the url (which come from the Drupal form with sort methods). I don't see any other way to do it efficiently. I can dig up some of my snippets, but I have provided the general outline of how to do it. Let me know if you have troubles at a point and I will try to provide an example.