One way to deal with this issue is to find the "90%" culprit that is causing fragmentation issue. You likely have a pathological condition in your code that causes the swiss-cheese effect.
Preliminary Actions
It goes without saying that you should first convince yourself that your high page usage is due to fragmentation and not due to a memory leak. :-)
If you haven't done so already, using the "Instruments" app in Xcode is an excellent way to watch your program allocate memory in the iOS simulator. Using the Allocations and Leaks tools lets you record every object allocation and malloc() your code does, along with handy timestamps. (And for free, the Leaks tool it will show you cycles in your object map if ARC isn't freeing memory like it should.)
Normally the tools keep track of memory that is still being used. You can select the Created & Destroyed option in the Allocations configuration pane to keep track of everything, which is viewable in pop-up right above the summary information.
There is also a VM page allocation tool that might shed some light on your issue.
Possible Remedies
Once you have determined the culprit, you can restructure your code to prevent the pathological condition. Or if restructuring is too expensive, you can mitigate the effects of the condition by reusing the memory.
Typically when the analysis shows that object allocation and deallocation is causing holes or a particular object is being allocated/deallocated at an alarming frequency, I take the offending culprit and make it into an object "pool".
This can be as simple as storing objects in an NSMutableArray and pushing and popping them as needed.
Of course you might want something a little more sophisticated that initializes objects when fetched, primes the pool with ready objects, and auto-refills with objects when it is empty or runs low. In iOS you'd also want to prune the pool if too many objects collect, or a low memory warning is received.
The nice thing is that this can be very generic code that you can reuse forever. :-)
Side Note
You mention the issue of not wanting to make objects Mutable. In some cases (like NSString) it can help with efficiency if you know (in advance) the space requirements and manipulations you'll need to perform on the string. That way you can tell it in advance how much space you'll need and operate on the string "in-place", reducing allocation overhead. (What NSString does under-the-hood is a whole other article. :-)