Thanks. I think I've looked into just about everything listed there already! At least two products that had IMAP support are no longer available, about the only thing left is PaPi-Mail.
I did try a free eval of it a while ago, and it was pretty bad

This time I did find a much better update, but it still has serious limitations as an IMAP client, as it's clearly been designed for POP than had IMAP bolted on. I've sent the author's some suggestions, I'll see what transpires.
An alternative would be a PDA-friendly version of something like Horde, but I don't know of anything. Horde itself is much too "busy" to be workable on a PDA browser (there do appear to be some embryonic hooks for PDA/Phone presentation, but nothing workable).
No more ideas I suppose?