The problem with epic level play as it stands, as far as I see it, is that there's no end point. The open-endedness is attractive on one level (No limits! Play the same character forever! No hard-wired end point to your advancement!), but it's also a huge disadvantage, since without an upper limit, there's no way to set a good scale. There's always SOMETHING BIGGER. I hit this problem more often than I wanted as regards feedback to the Demonomicon articles and Fiendish Codex I; no matter what CR one sets a demon lord at, it's too high for some folk and two low for others. Since you only have a starting point and not an ending point, it's VERY difficult to design anything for epic level. What's the difference between a CR 23 and 29 and 33 and 59 and 3492 creature? How do deities fit onto that scale? And if deitys DON'T fit onto that scale, then how tough does a character have to be to fight a deity? What CR is the most powerful creature in the Multiverse?
I agree with you in that this creates a problem of verisimilitude in regards to the power levels of various creatures in the campaign universe. If a scale is infinite, it's difficult (at best) to use it to measure anything.
That said, the problems of an infinitely-leveling system aren't only in measuring the power of higher-tier monsters. It also makes it harder to design classes. If all classes can gain levels endlessly, then you quickly have them losing any sort of unique or special class abilities - no one says that they can't wait to get to 117th level, because only then do you unlock Class Ability X that you've wanted for a while now. It's the main reason why, at epic levels, single-classing no longer makes sense. Admittedly, epic feats try to fill this void, but even they don't really stack up well when spread across infinite advancement. It's the same reason why WotC tried to design the epic spell system, letting you can create epic spells piecemeal at whatever DC you want, rather than having spells of ever-increasing set spell levels.
At the same time, having a closed scale of leveling also puts some fairly tight design constraints on things. For example, I'd recommend that if you make the game that way, you make damn sure that
everything in your game universe falls within this scale. Having levels be limited to just mortal characters, for example, with gods being outside of this scale, makes having a character that ascends to godhood feel almost like a punishment if you want to keep playing with that character - having to retire it "because the rules don't let you advance any further" is a bitter pill to have to swallow.
At the same time, that means that gaining levels - particularly at the upper end of the spectrum - shouldn't just be about gaining enough experience points. If you do put all creatures into your scale of levels, then creatures at the very top will be the most powerful creatures in the game universe; you shouldn't just be able to linearly progress to that point. There needs to also be a reason for scarcity of creatures at the upper levels of power. If every 25th-level character is a demigod (or equivalent thereof) then that quickly begins to feel not only boring, but also makes holes in the logic of the campaign world.
It's a difficult balancing act, particularly for Pathfinder, not only because everyone has their own set of ideas for what constitutes the limit of advancement (if any) in an infinite system, but also because you're also burdened with designing Pathfinder to be compatible with 3.5. My personal suggestion is that you basically eschew changing the existing epic rules, but rather institute a set of epic-level "guidelines" in regards to characters. That is, you have something like "no mortal race can ever gain more than 30 character levels, unless an individual is given patronage by an immortal power (e.g. a god, demon lord, fey ruler, etc). A character with immortal patronage may continue to gain levels, but if patronage is revoked, cannot continue to advance." This allows for epic level creatures, characters, and challenges, but keeps a tight leash on them - it also lets you design for a closed system of levels (e.g. you treat level 30 as the last level, so you can design new and unique class abilities for levels 21-30 for each class) while keeping options for potentially infinite leveling, probably as no more than a brief addendum.
That's what I think, at any rate.