I also don't think you have to disprove Godel's theorem to create an AI that thinks outside the box, however, I believe you would have to for it to be a rational agent. A rational agent by definition operates strictly within the domain of a formal system. Thus by definition, a rational agent is in direct conflict with the notion of "thinking outside the box."
Of course any simulation is implemented in some formal system, but that's not what I'm saying. I'm saying the inherent problem with a rational agent is that they maximize utility within a formal system -- that is what they do, that is their entire purpose. Once we start talking about rational agents that can "think outside the box", or think beyond the formal system in which they're defined, we're no longer talking about rational agents.
I agree with your belief that we may some day build AIs that think outside the box, I just don't see how it can be a rational agent. I think it will be much closer to a neural network, or probabilistic reasoning model, or some extremely "organic" or "fluid" device from which intelligent behavior organically emerges. Because if intelligence emerges from a strictly formalized framework, then Godel's theorems prove some very crippling limitations on what's possible within that fixed framework.
FYI there is definitely a connection between Godel's theorem and intelligence, though it may not be immediately obvious. I would highly recommend this as fun learning material: http://ocw.mit.edu/high-school/courses/godel-escher-bach/