The scenario you describe is handled in property graph model by the hyperedge pattern @Pangea mentioned. You essentially convert the edge (that needs edges in/out of it) to a vertex. With graphs I would think of it less as a denormalization and more of a different modelling abstraction.
As far as native support for edges on edges go, none of the graphs you tagged your question with directly support such a feature. As you did include Titan and OrientDB I assume you are evaluating TinkerPop as a possible part of your solution as well and I can further say that as Blueprints doesn't support edges on edges, none of the Blueprints graphs will either.
As far as traversal goes, I can't say I fully follow what you mean by "recursively traverse". If you could elaborate a bit, I could try to amend my answer. I'll add this simple example of how you would traverse from the "a" vertex to find all other related vertices in Gremlin (sorry, I don't know Cypher):
gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> va = g.addVertex([type:'N',name:'a'])
==>v[0]
gremlin> er = g.addVertex([type:'R',name:'r'])
==>v[1]
gremlin> vb = g.addVertex([type:'N',name:'b'])
==>v[2]
gremlin> vc = g.addVertex([type:'N',name:'c'])
==>v[5]
gremlin> va.addEdge('e',er)
==>e[3][0-e->1]
gremlin> vb.addEdge('e',er)
==>e[4][2-e->1]
gremlin> vc.addEdge('e',er)
==>e[6][5-e->1]
gremlin> va.out.in.except([va]).name
==>c
==>b
gremlin> vd = g.addVertex([type:'N',name:'d'])
==>v[7]
gremlin> es = g.addVertex([type:'R',name:'s'])
==>v[8]
gremlin> vb.addEdge('e',es)
==>e[9][2-e->8]
gremlin> vd.addEdge('e',es)
==>e[10][7-e->8]
gremlin> x=[];va.aggregate(x).out.in.except(x).loop(4){it.loops<2}.name
==>c
==>b
gremlin> x=[];va.aggregate(x).out.in.except(x).loop(4){it.loops<3}.name
==>d
In regards to:
If the answer is just to also create an edge between a and b while creating the hyper edge, then my question becomes: is there a good way to ensure that the edge and hyper edge are removed together?
When you remove the "hyperedge" vertex, you will automatically remove the edges connected to it, so you effectively remove them together.