How do we really know that this is actual deletion and not a deleted="true" in their databases?
We don't know that. If you're feeling charitable you could believe they're being honest, but if you not then you just have to wonder. There is no way Facebook could prove they don't have a secret server with your data on it somewhere. Proving that would be impossible.