Well it happens on the 3G connection as well, although the problem seems worse on the home router where indeed it is NATed.

I notice that the connection status in the status menu doesn't show a green circle like it does with google talk and skype connections, but a light brown or orange circle with clock hands inside. Could this have anything to do with it?