I have E63 Firmware: 200.21.012
Similar issue with E63, FV: 100.21.100 and with E51 (Do not remember Version)

I can setup SIP account, can place and receive Internet calls.
I'm not sure if it's important, but I'm using phone in Offline profile (w/o SIM card) and only using WiFi connection.

On Inbound calls (Calls to Nokia phone) everything is fine.

Problem appear on outbound calls (Calls from Nokia)

When phone sends invite out it reports following list of codecs as supported:

96 - AMR
0 - PCMU/G711
8 - PCMA/G711
97 - iLBC
18 - G729

If in response (SIP 200 OK) it got PCMU as chosen code - call is established fine

However if in response there is any codec other then PCMU,
Call on Nokia phone is dropped immediately with message:
"Internet telephone service not available"

Even PCMA - which is just another flavor of G711 call cannot be established.

If someone is interested, I can provide detail SIP trace.
The issue is 100% reproducible.