In the land of Aviontix there are ruins. A lot of ruins. There are many sand buried cities, king’s tombs (They were a very religious people, focused upon their leaving to the afterlife), and huge statuary. However, Aviontix was a kingdom so long ago, that everything has been looted. (Figure there has been a whole historical epoch or two since then) There might be a hidden tomb or something somewhere in the lands, but it is unlikely. This does not stop people from selling maps to them all the time.
A great treasure has been stolen from the Palace and taken to the nearby Temple to the Bitch-Goddess Atrath Klee. The King demands that the party go and retrieve it - the only snag is that the Temple is guarded by potent magic that will kill any male who steps inside. It's just as well that the King has a stash of Girdles of Gender Alteration for just this circumstance.