I tested the *same* configuration with another PC
which has the latest -current with very little
differences to GENERIC (pf enabled).

And it worked. The strangest thing is that when
I do tcpdump on the external interface of the
problem machine, I see 10-addresses being used
as the source address, while on this other PC
I see correctly NATed source addresses, and
everything is working perfectly.

This really beats me, but I'll continue the
debugging...

Teemu