[eluser]barbazul[/eluser]
I think the answer to all your problems is to use memcache.
First of all, don't use php native sessions for your server structure because they use local files for storing data and each server won't know what data is being held on which other server. That's also the main reason to fall back to cookies, it wont matter which server processes the request because session data will always be available.
I also understand why you don't want to use the db for this.
So I would say you should definitely move forward with Memcache. Seems like the best solution to all your problems
In case you (or someone else reading this) don't know how memcache works, its simple: A memcache server has a certain amount of memory to store data on a key-value basis.
As its a different server to which all servers connect to, all of the will have access to it and the information stored will be unique.mo.
Memcache also comes with a module to replace php native sessions which i never used but seems like the optimal solution
Hope you find this useful