OK, this is probably the weirdest problem I've ever encountered in a LONG time...
I was checking why I can't seem to be able to log-in to SIP services over a 3G network. Naturally I suspected my cellular provider for blocking VoIP, as SIP seemed to be working fine over WLAN. After my provider strongly denied blocking any data traffic, I took a tcpdump output and looked at it. After glancing at it for about half an hour, I found the problem:
I'm running, for unrelated reasons, an OpenVPN client on the phone. Seems that the IP stack got mixed up and was sending the SIP UDP packets on the 3G interface, but using the VPN interface's IP address as the source IP for the packets (this should NEVER happen!). If I take the VPN link down, then SIP works fine over 3G.
Even weirder is the fact that anything other than SIP seems to work OK, and even SIP works when using WLAN instead of 3G (even when OpenVPN is running).
What do you think? Did I hit a really obscure bug or something?

It's a known bug since Bora, it will probably never be properly fixed in Maemo but see the bug page for possible workarounds.

No, it's probably a different bug as I don't want the SIP traffic to go through the VPN, I want it to go "normally" over the 3G connection.

Anyway, I found a little dirty solution for the problem: Install kernel-power and the iptables package, then do:
iptables -t nat -A POSTROUTING -o gprs0 -j MASQUERADE
This hack makes sure all outgoing packets on the 3G link use its own IP address. I also use the old Debian-Woody iptables startup script to get this configuration to survive reboots.