Is this problem over wifi or 3G? or both? If this happens on your personal wifi network, check whether SIP ALG is enabled on your router. If it is, disable it - it usually creates more problems.

Your phone is likely NAT'ed and the SIP proxy will want to keep the NAT open by sending a keep-alive; and your SIP UA will also be prompted to reregister periodically. When you say you tried changing the keep-alive settings, what exactly did you do? and which keep-alive mechanism are you using? (OPTIONS ping is usually a safe bet.)