Really, POJO cache needs a proper SortedSet and Map. There's already a bug you can vote on.
If I'm feeling inspired, I might work on this myself...
And yes, your work around would be helpful, but if the underlying data is not sorted property, I don't really see it working very well...
Yes, support for different flavor of Collection classes in PojoCache has been in my mind for a while. TO fully address this, I have just created a jira and put my thought in there:
Please check it out. Of course, as genman mentioned, if you want to your own flavor of SortedSet, you will probably need sorted node underneath for performance.
As for the CCE, you can file a bug for future reference and a junit case will be nice as well.