It seems that these Fastmail guys are primarily charging for storage. My question would be, do they allow to set up many different domains and email addresses inside a single account or is this a one email address/domain per account thing?
Yes, you can use as far as I can tell an unlimited number of domains and aliases in a single account. Another plus over Google Apps is that the aliases are domain-specific (as far as I could tell, aliases for Google Apps applied to all domains).
I've been on the "Enhanced" plan for years now and have at least a dozen domains and maybe a dozen and a half email addresses configured. FM will also let you (if not encourage you to) to use its DNS servers instead of your registrar's, but that's up to you. I generally use FM for DNS hosting but you absolutely do _not_ need to do this to host domain mailboxes with them.