I'm not completely familiar with how py2neo determines if a node exists in the database or not, but you may want to try to use the new indexes introduced in Neo4j 2.0.0. The indexes you are using here are the legacy indexes which require you to manually keep them up to date, and there are several caveats around their operation. The new indexes are automatically kept up to date and work more as an optimization for your queries, in the same manner indexes work in relational databases.
I'm not sure how or if py2neo exposes these indexes directly, but you can access them through py2neos cypher API. It's generally a better idea to use the cypher query language when working against the neo4j server, since it allows you to send larger chunks of domain work to be done in the database, rather than pulling data out one http call at a time and doing the work on the client side.
For instance:
from py2neo import cypher
session = cypher.Session("http://localhost:7474")
tx = session.create_transaction()
# Create an index
tx.append("CREATE INDEX ON :User(name)")
tx.commit()
# Query that will use the index for lookup
tx = session.create_transaction()
tx.append("MATCH (n:User) WHERE n.name='Cat Stevens' RETURN n")
results = tx.execute()