EDIT: See next post for possible setup. I'll leave this one here in case it doesn't work.
I looked over the fastmail site. Interesting. I like the clean no-nonsense design.
I don't see way for you to sync the Contacts app with fastmail through the web. Other than MobileMe, only accounts that can be set up as Exchange accounts will sync with Contacts(so far as I know) {turnes out what I knew, was wrong}. I only saw POP3, IMAP4, and SMTP supported.
If the site will sync with Outlook, you can use iTunes to sync your contacts on the iPad and iPhone with Outlook, but it won't automatically update. You'll need to manually sync each device every time you want to update the data. I don't care much for this method. It often leads to conflicts when more than two devices are involved. Not a big problem, but annoying.
The site seems to be a pretty clean HTML site though, and I saw something about mobile phone support. You could probably just use Safari with the site. I doubt that's a good solution for you, but I'm not able to come up with another one that won't use one of the services you want to avoid.