Esaka is where the company headquarters are, so I've always seen Esaka as the theme of SNK in general, more than just Kyo specifically. "Goodbye Esaka" is the only song to directly reference the state of the company, however.
Tears is a great Kyo theme. I prefer Goodbye Esaka. But there are lots other good ones. I'm fine with whichever one SNK picks. Although the XII version of Esaka would be a good choice, just because it's a great one that's never been used in-game. It really shouldn't go to waste.
Didn't know that Rex; makes a lot of sense now looking back to around 2000.
Any of Kyo's theme's work for me for Ex Kyo, though I'm in the camp of Tears because it's awesome (goes without saying), and because it's reminiscent of IMHO his best theme, best outfit, and best moveset, all debuting in the same year; hence, NESTS Kyo.
And for everyone calling out the best KOF theme, let's do that here:
http://dreamcancel.com/forum/index.php?topic=1461.0