You can store mail locally with IMAP but that's a function of the mail client your using rather than a part of IMAP itself.
You just have to get your head around thinking of it all as happening on the server - you're changing what's on the server so those changes will reflected when another device s used.
I had a quick look at Fasthosts and they don't charge extra for IMAP per se, but you need to remember all your mail stays on the server, attachments and all, so a 100MB mailbox won't go far. All depends on the mail you send and receive.
Seeing as you've already paid for Outlook on Mac (presuming you have one of the 5 licences free) I'd use that - just follow the procedure outlined in the Dummies link.