I have much academic experience with some of this, especially the second part of your question. I'll address a few different sides of things.
The most drastic way I can think of that could ostensibly be caused by some natural occurrence would be a low altitude meteoric air burst similar to the Tunguska event. Such an event would cause a lot of surface damage without necessarily leaving a crater or other easily identifiable visible mark.
As you've removed your restriction against volcanic activity, you might consider pyroclastic flows as one possible means of destroying your city, with conditions less like those experienced at Herculaneum and more like those at Saint-Pierre.
However, natural disasters on a city-destroying scale generally leave telltale signs behind. So if the air burst notion doesn't fly for you, and if you truly need it to be impossible to determine what caused a city to be burned to the ground, I would suggest staying away from something like a volcanic eruption and perhaps finding a more mundane way to explain a massive fire. Something as common as a bolt of lightning could very well start a fire that spreads out of control, if the conditions are right. Not very exciting, but it could get the job done.
Now specifically to the second part of your question: Many large settlements have been totally wiped out by fire. What you're describing, though, where literally nothing is left 24 hours later but ash, is somewhat more problematic. When something that big burns down, it can leave pretty noticeable remains for a very long time, especially if the area is relatively undisturbed. (Researchers can identify things like tiny campfires older than the time frame you're describing.)
But, say, if the area was abandoned after the catastrophe and later re-inhabited, then evidence of the event could be very difficult to come by. Disastrous episodes or not, people tend to tear down the old and rebuild over it with the new. Additionally, with whatever you do find, it can be problematic knowing whether it was disturbed or altered in some way by more recent inhabitants, adding to said uncertainty.
Likewise, as others have pointed out, water is great at eroding evidence, but it still can leave some traces, which you may find desirable (i.e, your stated "clues that make them wonder" aspect). The nature of the flooding itself, such as whether it's a permanent feature (e.g., a lake), etc., can make a lot of difference. The evidence that is left behind for people to find might depend largely on the nature of the flood itself. (On a related note, you mention your city is above sea level. If that's not a hard requirement, it would be simple to explain a flood if your city was below sea level.) I won't belabor this here; if you want more information specifically about this particular facet, just let me know.
Letting nature run its course will help obliterate much of whatever evidence is left. A semi-arid climate may not be as ideal for obscuring evidence as, say, a jungle, but weather effects and natural geologic processes will certainly contribute to eliminating material remains left after the city's destruction.
If ultimately your chief concerns are to totally annihilate a city and have it be hard for people later to determine exactly what happened, then if you can relax the requirement on a complete "ashes to ashes" situation, you can in fact achieve a realistic scenario that meets your goals: Even if you don't completely demolish the city to the point of literal ash, you can easily meet your requirements for not leaving many traces behind by simply having the area be re-inhabited by people later, or having the site be covered by water. Flooding aside, allowing nature to run its course will generally do much to cover the catastrophe's tracks.
Additional Info - Regarding your question specific to an air burst (moved from comments):
With Tunguska, the object causing the explosion itself left virtually no traces behind. It was essentially completely vaporized. Even in-depth analysis of the soil doesn't really tell us much. So, if we're talking about finding any tell-tale indicators of something like that in the archaeological record thousands of years later, in a semi-arid climate, with all the natural processes present there? Then yes, it's extremely unlikely we'd be able to tell anything about the object that exploded, per se.
The one thing I wonder about is the blast pattern it might leave behind. But as long as the city isn't sprawled out over a ridiculously a huge area, most of the force of the blast would impact structures vertically rather than horizontally, and that's a plus. If the building materials are things like mud bricks, I'm thinking things could be pummeled so badly by the blast that in 4,000 years, you'd be left with little more than rubble to dig up, with the occasional large chunks. Things further out from the center will be affected less, but on the scale we're talking about, pretty much nothing would be left.
And, yes, there would be lots of fire.
Anyway, to sum up, without totally obliterating the surrounding geography with an obvious crater, I think people might suspect the city was demolished in some way, but it'd be near impossible to tell anything for sure. If you want to toss in some extreme weather in the aftermath, I'd lean toward tornadoes, to further muddle things up.