Anyway, I'm a bit unhappy about the requirement of full evaluation order independence, because even the purest of pure languages (e.g. the untyped lambda-calculus or PCF) don't have full evaluation order independence. I guess you mean evaluation order independence modulo termination?
My intuition is that pure means that all language expressions M can always be evaluated locally by just looking at the meaning of all subterms of M. In terms of Hoare logic (for total correctness) that would mean that the pre-condition speaks only about the termination of the free variables of M (sorry for being so terse, I think this can be made formal).
The notions of purity I was pointing at was any that entailed the restrictions in the paper you'd linked. There are restrictions of Haskell that are pure in those senses, but Haskell taken as a whole is not, even without invoking anything unsafe.