Я пробовал вариант вашего кода с использованием «современного» игрушечного графа, и ваш код оказался для меня правильным. Я считаю, что следующее отражает дух того, что вы делали:

gremlin> g = TinkerFactory.createModern().traversal()
==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard]
gremlin> g.V().property('version',1).iterate()
gremlin> name = 'marko'
==>marko
gremlin> oldVersion = 1
==>1
gremlin> version = 2
==>2
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>edited
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>same
gremlin> name = 'stephen'
==>stephen
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>same
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>same
gremlin> oldVersion = 2
==>2
gremlin> version = 3
==>3
gremlin> 
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>edited
gremlin> g.V().has('person','name',name).
......1>   fold().
......2>   coalesce(unfold(), 
......3>            addV('person').property('name',name).property('version',version)).
......4>   choose(values('version').is(oldVersion),
......5>          property('version', version).constant('edited'),
......6>          constant('same'))
==>same
gremlin> g.V().has('person','name','stephen').elementMap()
==>[id:19,label:person,name:stephen,version:3]

Я бы посоветовал немного упростить ваше описание проблемы. Вы заявили, что проблема заключалась в следующем:

Не удается создать вершину, более поздний запрос не может ее найти.

Правильно ли работает, если убрать логику choose()? Другими словами, сможете ли вы заставить работать базовую операцию upsert? В противном случае проблема кажется изолированной для этой части запроса, хотя то, что у вас есть, похоже, соответствует рекомендуемым методам, поэтому я не уверен, что может быть не так.

Приведенный ниже код в gremlinjs обновляет вершину, только если свойство номера версии совпадает. Это обеспечивает безопасное чтение-изменение-запись вершины с использованием оптимистичного параллелизма (т.е. коллизии должны быть редкими, или вам следует сделать что-то еще)

Код доступен как суть: https://gist.github.com/pszabop/3b07fa7caadf1dbd86d86

//
// o.id o.__version, and o.__lastUpdate have special meaning or are reserved
//
graphdb.upsertVertexVersioned = async function(type, o) {
  const g = traversal().withRemote(this.connection);
  let oldVersion;

  // don't modify original in case of exceptions
  // return the new object and let user decide to reassign or not
  o = Object.assign({}, o);

  if (!o.id) {
    o.id = uuidv4();
  }
  if (!Number.isInteger(o.__version)) {
    o.__version = 0;
    oldVersion = 0;
  } else {
    oldVersion = o.__version;
    o.__version++;
  }
  o.__lastUpdate = Date.now();

  // @see http://tinkerpop.apache.org/docs/current/recipes/#element-existence
  // @see https://stackoverflow.com/questions/58513680/in-gremlin-how-do-i-modify-a-vertexs-properties-only-if-a-version-property-mat
  // The pattern we are using is keys get copied into properties that can be used
  // by the graph database for its work, and then the
  // entire object is JSON serialized into a generic `obj` property.
  // XXX TBD use graphson?
  const v1 = await g.V().has(type, 'id', o.id)
  .fold()
  .coalesce(__.unfold(),
    __.addV(type).property('id', o.id)
    .property('version', o.__version)
  ).choose(__.values('version').is(oldVersion),
    __.property('lastUpdate', o.__lastUpdate)                  // updated properties go here
    .property('version', o.__version)
    .property('obj', JSON.stringify(o)).constant('edited'),
    __.constant('unchanged')
  ).next();

  if (v1.value === 'unchanged') {
    throw new Error('version mismatch, vertex not updated');
  }

  return o;
};

test('test vertex versioned upsert and get', async function(t) {

  graphdb.open();

  // initial write and verify
  const o = { randomText: uuidv4(), foo: 'bar'}
  const osent1 = await graphdb.upsertVertexVersioned('testtype', o);
  t.ok(osent1.id, 'a random ID was assigned');
  const oget1 = await graphdb.getVertex('testtype', osent1.id);
  t.equal(oget1.randomText, o.randomText, 'random text was as written');
  t.equal(oget1.id, osent1.id, 'ID was as assigned');
  t.equal(oget1.foo, 'bar', 'field foo is "bar"');

  // make sure version gets updated when field foo is modified
  oget1.foo = 'beyond all repair';
  const osent2 = await graphdb.upsertVertexVersioned('testtype', oget1);
  t.equal(osent2.__version, 1, 'version was changed from 0 to 1');
  const oget2 = await graphdb.getVertex('testtype', oget1.id);
  t.equal(oget2.randomText, o.randomText, 'random text was as written and was unchanged on second write');
  t.equal(oget2.id, osent1.id, 'ID was as assigned');
  t.equal(oget2.foo, 'beyond all repair', 'field foo was changed to "beyond all repair"');

  // if we are using a stale copy of the object an update should not happen
  osent1.foo = 'illegal update';
  try {
    const osent3 = await graphdb.upsertVertexVersioned('testtype', osent1);
    t.fail('should never returned from an incorrect version update');
  } catch (err) {
    t.ok(err.toString().includes('not updated'), 'error message is correct on illegal version update attempt');
  }
  const oget3 = await graphdb.getVertex('testtype', oget1.id);
  t.equal(oget3.randomText, o.randomText, 'random text was as written and was unchanged on second write');
  t.equal(oget3.id, osent1.id, 'ID was as assigned');
  t.equal(oget3.foo, 'beyond all repair', 'field foo was unchanged after failed update');
  graphdb.close();

});