I'm in favor of this, but I'm also in favor of the server running smoothly...
Currently it seems, as many have said, that the list is case-sensitive alphabetical, and displays left to right - so if you read down one column and then down the next it will still seem random. Of course, this sorting is secondary to the status sorting of being "online", "passing-through", or "offline".
To identify "valid pvp targets" would mean determining the vitality of each person's creatures, since too low vitality makes you invalid. This would require more effort from the server, and I'm against that. I think sorting by MP would be most efficient. While putting those matching your current MP at the top might seem nice to some, it's still now at least 3 different orderings (more as higher MPs are added). My favored implementation would be to display in columns instead of lines, with a divider line between MPs.
Adding an option to exclude "offline" characters from list could save some space.
Also, I think it might be helpful to mix the "passing-through" and "online" people together, and here's why:
With the current list, you may be surveying a number of potential targets... then the list updates. Visually, it can be hard enough to find these people again in the list - they've often changed columns, they may have changed rows, they may have left the area entirely. If they left the area and changed to "passing-through" status, they won't alter the layout of the list, only those that are "passing-through" that expire from the list (or anyone that logs out) would change the layout and seeing those mixed in with the "online" names will allow you to expect the change. If you've used AIM, and seen when someone logs off, there name turns italic before it disappears - I like that, at least so far in the fact that it's a cue of what to expect next. I'm not asking for all that mind you, just my suggested watered-down version of it.
... and timestamps in the chat.