Here's the problem: Some email-service providers (like
Google) have more than one server and distribute the load such that, e.g. the incoming mail server imap.gmail.com is assigned to more than one IP-address.

With stateful rules, the ipfw firewall correctly allows outgoing packages to one of the IP-addresses of the mail server. However, packages to the same port but to a different IP-address are consistently rejected.

I suspect that following the establishment of the initial connection, dynamic rules tables will not match because of the inconsistent IP address, and therefore outgoing packages to the second IP-address are always denied.

Does anyone know a solution to this problem?
Many Thanks.
Here are the relevant parts of my rule set:
...

#allow packet through if it has previously been added to the dynamic rules table
ipfw -q add 0010 check-state

#allow out get & send email function
ipfw -q add 0040 allow tcp from any to any 993 out via $nic setup keep-state
...

And here's the log:
Aug 3 18:44:33 xxx Firewall[38]: 42 Accept TCP my.ip.address:50201 209.85.147.111:993 out via en1
Aug 3 18:44:33 xxx Firewall[38]: 70 Deny TCP my.ip.address:49866 209.85.199.109:993 out via en1

Usually, a mail client might resolve more then one IP for the same hostname, but it will connect to only one of those addresses for the duration of the session. So it shouldn't be a problem for your dynamic rules.
Your first log entry states rule 42 while in your ruleset rule 40 is the that should match.
do you use nat?