Well yes, it is horrible, but not nearly as horrible as I originally thought.
Once again, I misinterpreted a part of the spec. You do need to reopen the InputStream if you want to seek() back, that's true, but. If you keep a FileConnection object for the file in question, you can call getInputStream() on it as many times as you want - the security prompt is shown only for first access, then the phone is supposed to remember that you already have permission to do that (and it appears that many (if not most) phones actually adhere to this).
I assume that this holds true for other functions on a FileConnection as well, but I didn't test that yet.
Oh, and that RMS caching idea I had was slow and stupid.