SAND IT'S EVERYWHERE!!

[Veknironth]

Well, it depends on the materials or magic used to construct the fortress. If it's regular stone, the combination of wind and sand could erode it in a few thousand years. However, if it is somehow protected from erosion then it could be buried under the sand. Wind blown sand would essentially pile up on the sides as it blocks their flow across the land scape. Over thousands of years it could be buried entirely. Or, if the story requires it, it could be exposed by a sand storm that blows a dune off of the top and exposes a parapet, tower, or even a low lying section of the keep.

Now, if it's been buried for a long time it limits what is living there. It's possible that the dead servants of the Warlocks and perhaps the Locks themselves are unliving underneath. It could have been located by some subterranean species who have been using it as refuge from the storms that ravage the area. If it's still standing it seems the Gromek would have requisitioned it.

-Vek
"A big fan of waste, you must work for Parliment."

[Northern Ranger]

Put a psychotic old dwarf running around the place, killing anyone that enters. He could be a rune smith, the last known of his kind, but he's lost touch with reality so much that he has no recollection of his skills. How he has survived all these years would be another mystery for the players to solve.

[krate]

you can do whatever you want to. that's the beauty of rpg's! do whatever seems cool and fun and will be enjoyed by your gaming group.
How much of the ruins will be left in the waste? whatever seems cool. it's a magical and fantastical world. the players can encounter a few sandworn stones, just remnants of a once great fortress. or they can encounter a full and complete structure, eerily quiet with no sand or damage done by the elements and time. maybe the ruins can only be seen on a night with a full moon or under other special conditions. go nuts with it and have the players delve into it's history and legend and have them put it together so they can find it and explore it.
who's dwells in there? anything from a dragon to mad warlocks and undead. your limited only by your imagination. maybe the warlocks still rule there, consume by their magicks and madness. maybe the elementals have grown tired of being trapped there forever and it is they who somehow have gotten the players to come and find and explore this ancient edifice in order to be set free? maybe the original creators are gone and it now serves as a home to minotaurs who use the place as a base for raiding, and since the structure is magical and elusive, the minotaurs can not be found and their raids halted.
you can do so much with this simple idea. don't worry about realism and what real ruins would look like after 500 years. this is a place where magic and dragons are very much alive. so have fun and let your ideas flow.
if you have access to PF book 9: baalgor wastelands, you can find some cool history there, monsters that dwell in the wastes (some which were originally summoned during the great elf/dwarf war!) and rules for traveling in the desert. it's an invaluable resource and great read.
have fun with your idea and happy gaming.

[The Dark Elf]

Warlock ruins =

Clay animals!
Golems
Several high spec booby traps

And maybe the original creator somewhere with the transfer essence spell (cant recall name atm)