Does bmesh guarantee order of vertex in a edge according to the time they were added
The order of both vertex indices stored in an edge (me.edges[#].verts), or the vertices references respectively (bm.edges[#].verts) should not change unless you make it so (by flipping an edge I guess).

That is because the order is important. Think of a line of 3 connected edges: if you flipped the vertices referenced by the middle edge, it would still look like the same edge. But both vertices would need to be switched (as in coordinates) - but that doesn't work because they are used by other edges.

(Unscientific) stress test:

import bpy

for area in bpy.context.screen.areas:
    if area.type == 'VIEW_3D':
        break
else:
    raise Exception()

ctx = bpy.context.copy()
ctx["area"] = area
ctx["region"] = area.regions[-1]
bpy.ops.ed.undo_push(ctx)

ob = bpy.context.object
me = ob.data
bpy.ops.object.mode_set(mode='EDIT')
print()
print()
t = {}
for e in me.edges:
    v1, v2 = e.vertices
    t[(v1, v2)] = "{: 8.4f} {: 8.4f} {: 8.4f} | {: 8.4f} {: 8.4f} {: 8.4f}".format(*(me.vertices[v1].co[:] + me.vertices[v2].co[:]))

bpy.ops.mesh.sort_elements(type='RANDOMIZE')

bpy.ops.ed.undo_push(ctx)
me.update()
bpy.ops.transform.translate(value=(0,0,2))
bpy.ops.object.editmode_toggle()
bpy.ops.object.editmode_toggle()
bpy.ops.ed.undo(ctx)
bpy.ops.mesh.sort_elements(type='RANDOMIZE')
bpy.ops.mesh.flip_normals()

for e in me.edges:
    v1, v2 = e.vertices
    if t[(v1, v2)] != "{: 8.4f} {: 8.4f} {: 8.4f} | {: 8.4f} {: 8.4f} {: 8.4f}".format(*(me.vertices[v1].co[:] + me.vertices[v2].co[:])):
        raise Exception()


The order of geometry elements is not guaranteed on the other hand (me..index / bm..index), although it is practically stable, as long as you add and remove in stack principle (last in, first out).

If a vertex / edge / face other than the one with the highest index is deleted, all elements with a higher index will shift to fill the gap.

There are also mesh operations to sort mesh elements based on properties like distance to camera, or randomize the indices even.

You could use a custom data layer to store an explicit order (e.g. bm.verts.layers.int), but beware of the value propagation: if you extrude a vertex for instance, that custom data will be carried over to the new vertex.

This patch might be interesting for you: https://developer.blender.org/T42865