In Neo4j 1.9.M02-M05 you cannot delete nodes and relationships which stem from cypher queries outside a transaction.
For details, see this article on SO:
/cc @boggle I think this should be resolved now, right? Cypher always returns NodeProxy objects, which would work fine to be used as outlined in that example
Since Neo4j 2.1 (perhaps even 2.0) use of transactions was made mandatory so in order to delete a node you have to be in a transaction. That node proxy may very well haven been obtained by running a Cypher query in a previous transaction.
Closing this as it should be resolved in all maintained versions. Please re-open if the issue remains.