I had some initial troubles with 2talk and my new Gigaset A580IP.
It would only register for a short while, then fail.
While it was registered incoming calls were never connected to the A580IP.
2talk was behaving correctly as it sent me to voicemail at the appropriate time.
It turns out it was my router (Linksys WRT610N) being a less than stellar SIP citizen.
My router had a broken SIP ALG implementation and broken SIP ALGs can be found in a bunch of routers from different vendors. This may explain why changing router/gateway devices sometimes solves this issue.

Solution for Gigaset A580IP + Linksys WRT610N:

  1. Upgrade the WRT610N's firmware to Ver. (adds option to disable SIP ALG)

  2. Disable SIP ALG on the router

That was it. 
Everything now works as expected. :)

More info about SIP ALG and dodgy router implementations here: