Here's a jsFiddle with an example of the problem.
http://jsfiddle.net/Jq2HR/
In making that I learned that the issue only exists when sortGrid is executed within the loadComplete event handler. If it's executed separately then subequent navigation works fine. So whatever is happening that's messing up the behavior must be running internally after the loadComplete event fires, but since that's the last event in the data loading process, there's no option for me to execute sortGrid any later.
The only remaining option I can think of would be to set a timeout in loadComplete to execute sortGrid after jqGrid is finished doing whatever it does after that event. Seeing as though I'm just trying to fix a subtle visual this is a possibility, but might fall out of sync if a user paginates quickly, so clearly not ideal.
IMO the best solution would be for jqGrid to support server-side sorting defining. So if the server provides sort/order variables (or whatever is defined in prmNames) in the response, those will automatically overwrite whatever jqGrid already thinks sorting is. The server being the authorative source over how the data is actually sorted, it makes sense that it could tell jqGrid that for proper presenation. I actually expected this behavior to exist already and have returned sorting information this whole time…