Should FaceTime work without a defined Proxy Server on restricted networks?
This depends on the limitations you have in your network. If you're only limiting HTTP traffic and forcing the clients to go through a web proxy, then you're probably not cutting off FaceTime's custom TCP and UDP connections.

The exact protocol for FaceTime hasn't been released to public by Apple, but they do publish a guideline regarding network configuration (open ports) needed for FaceTime and iMessage: http://support.apple.com/kb/HT4245