This is why the sidechains paper suggests a one-off change to Bitcoin might be needed: there's no out-of-the-box Bitcoin feature to validate this proof. The authors propose an interim measure where n-of-m "functionaries" are trusted to validate the proof.
https://github.com/orisi/wiki/wiki/Orisi-White-Paper http://gavintech.blogspot.com/2014/06/bit-thereum.html
Basically, you choose a panel of up to 15 independent entities to verify that the funds were locked indeed. The panel can be modified by a majority of votes if some of the entities prove to be unreliable - kind of like the Supreme Court works.
This obviously introduces a new vulnerability to the system, but is the best solution available right now.
To be clear, IMHO it is a mitigation or heuristic, not a solution at all.
Disclaimer: slightly disgruntled and provokative because I don't really understand the technicalities and a lot of hype makes it even more unbelievable.