Inserts are also quick if you do maintain order, simply by maintaining a pointer to the end of the list. You've only two pointers to update for the list (end of list and pointer to end of list) or am I forgetting something? Deletes could be sped up by making it double linked, and I can't think of why you'd ever need to perform a search... even if you needed to find a particular processes own structure for a page, seems like you'd start the search from that processes page table which can be done in a determinate amount of time, rather than from your own and then through the linked list.
I don't know what other property you could be looking for, other than memory address or process id, that you could use as the value for an index or hash. If you were collecting a stat (such as the process that's using the page that runs the most, which could be a useful thing to know) you'd have to iterate through the lot. Maintaining an index of that value is loads more work that I can't see paying off. What other value, other than page address and process id, would you want to search on?