I've used both. Titan is not anywhere near production ready. And now it seems like they won't ever be. It's not even a real database. It's a library. You can't even delete indexes once you create them. I don't get why anyone would go with them. (Is this still the case or did they resolve that index issue?) Either way, OrientDB is more mature/stable and was much faster than Titan. Then, OrientDB is a multi-model, so it just has so much more capabilities compared to just a graph database. IMHO, Titan seemed like a toy in comparison.
We started a project a while ago using Titan that is starting to come to fruition, and we went with Titan because it looked to be one of the only options that could scale to where we needed (around ~500M vertices, probably 10x that in edges) and worked on top of our existing infrastructure (HBase). Neo4J definitely wouldn't work for that, though looking at OrientDB again it seems like it might, though we'd have to figure out the operational implications of a new clustered technology.
Fortunately we've been using the Tinkerpop API so it should be fairly inter-changable on the back end, we're definitely going to have to look into other options now that Aurelius has been acquired.
I don't know where you got the impression from that Neo4j can't handle graphs of this size. We have users and customers running much larger graphs in production. So that _definitive fact_ is not true :)
I'm willing to believe that Neo4j could handle it (admittedly this research is 18 months old), but everything I see about the Neo4J licensing model indicates we could not link to it without also opensourcing our code, which is a no go for us.
I didn't have any performance issues with OrientDB, but it's worth noting that I worked with relatively small datasets (e.g. graphs with ~1000 edges).
Titan, given that it runs on HBase or Cassandra, is on a whole different level compared to these two graph DBs. If you're working on a small app which needs an ebedded graph DB, you'll definitely not use Titan.