Если ваша система работает по HTTP-протоколу, то вариантов целая куча: начиная от Comet и WebSocket, заканчивая банальными RSS-потоками.

Если же всё работает на более низком уровне, то смело берите UDP или TCP; и NAT здесь не проблема: в игровой индустрии давно умеют с этим броться.

Не забудьте про ботоводов. На dtf.ru была не плохая статья на эту тему. Вообще, рекомендую полазить по данному ресурсу, т.к. можно много интересной информации накопать.

Ещё хотел бы добавить, что чистое шифрование не поможет, об этом упомянул вскользь korvindest, но я уточню. Даже не расшифровывая сам запрос, мы может понять что при отправке пакета X на сервер происходят определённые действия. И этим легко воспользоваться при любой автоматизации действия, в то числе и при читерстве. Поэтому в данные нужно подмешивать некоторые уникальные IDшники, которые будут постоянно обновляются.