Some of our use cases might perform much better with edges if we used the indexes. My original understanding was that edges are indexed by default, but it turns out not to be the case.

The edge indexes can be added using Titan-specific API:
http://s3.thinkaurelius.com/docs/titan/0.5.0/indexes.html#vertex-indexes

One of use cases where it could help significantly (if it works as assumed) is links from an app to its files.