Earlier in the game, I received a few units from allied CS Valetta. The odd part is that these units were H'wachas, a Korea only unit. There was no Korea in this game to gift it to them either. How does this work, and how did it happen?
City states can gift any unit, including unique units (of civilizations not in the current game). For instance, if you have the patronage policy resulting in occasional Great People gifts, you might be given Khans.
From the Civ5 Wiki:
Militaristic City-states have also been updated in Gods and Kings, giving them ability to gift you unique units from other civilizations (for example, the Chu-Ko-Nu, a Chinese unique unit).
You can see which militaristic city state can give what unique unit in that CS's diplomacy screen.