I'm not familiar with all of the settings, but if you think it's a NAT problem, shouldn't you have NAT Keepalive enabled?
Unfortunately, I don't have enough experience with this to help much further, but I still think it's an internal problem. My logic is that I don't think the 3300 would produce a log like that if it actually sent an Offer out, but didn't get a reply. Calls fail quietly in the system all the time.
One sure way to tell is to do a Wireshark capture at the output of the 3300. Make an outgoing call and make sure that you see the SIP Offer going out (and an Answer coming back). If you do, then keep following the trace through the various pieces of your network. If you don't see the Offer, then it's still some programming in the 3300 where the call control doesn't know where to send the request.