Ymitury
Mentioned in passing in The Colour of Magic and completely forgotten until The World of Poo, the assumption was that this was one of the "joke countries" that Terry created as one-shots, back in the days of the fourth book in the series when the title-page disclaimer was "This book has no map. If this bothers you, feel free to go and draw one of your own" (Sourcery).
However, in the current The World of Poo, there is a very definite and clear mention that Ymitury exists in the "modern" age and cannot be dismissed easily. It is apparently a Sultanate, whose Sultan is slap bang alongside the idea of polygamy and open relationships. He is so open, in fact, that on a state visit to Ankh-Morpork, he gifted Vetinari six surplus-to-requirements concubines. Although they were bound head to toe in black ribbon, and the Patrician was assured they'd break out of the coccoon stage and turn into finest specimens.
Ymitury has, or had, an Archmage; but he can't have been that good a wizard or he would not have allowed his Staff to be robbed, and by mere Thieves, at that.
Located on the coast of Klatch just Hubwise of Howondaland and Rimwards of Hersheba.