Edward V of England might qualify. He was never technically coronated but he was the recognized heir to his father, Edward IV. Edward V was only 12 at the time and his uncle, Richard III assumed the role of regent. Richard kept delaying the coronation while meanwhile word spread that Edward V was the result of a bigamous union thus making him and his younger brother illegitimate and conveniently leaving Richard III as the rightful heir.
Edward V and his brother Richard went in to the Tower of London and were never heard from after the summer of 1483. To this day, historians can only speculate as to their fate although the most common theory is that they were murdered.
Other cases of "recently deposed royal/inconvenient heir is imprisoned and never heard from again" exist such as Louis XVII of France (the "lost dauphin") who spawned dozens of pretenders.
If you mean "without a trace" to apply to the people the sovereign was governing (i.e. we today know what happened but the citizens then did not) and you stretch the "head of state" bit to mean "head of state until very recently prior to disappearance." I think Tsar Nicholas II's brother Grand Duke Michael Alexandrovich might qualify. Nicholas abdicated the throne in February 1917 and then abdicated his son Alexei's claim to the throne (due to Alexei's haemophilia). Nicholas' brother was proclaimed Emperor. The provisional government at the time didn't actually agree to that, but as Wikipedia says "the legal position was complicated as the legitimacy of the government, whether Nicholas had the right to remove his son from the succession and whether Michael actually was Emperor were all open to question." His status as "head of state" was murky from the start, but I think it at least falls within the realm of what you were asking.
The provisional government fell to the Bolsheviks and Michael was imprisoned and sent east to Perm. By June 1918, the local head of the secret police decided Michael should "disappear." Michael was murdered and "the Perm authorities distributed a concocted cover story that Michael was abducted by unidentified men and had disappeared." The story was successful enough that "Soviet disinformation about Michael's disappearance led to unfounded rumours that he had escaped and was leading a successful counter-revolution."
