I just realized I overthought the caching scheme, and removing one check made it 3x faster :)

  function getLongestPathCached(nodes, nodeid, visited, depth) {
    var idx;
    visited |= 1 << nodeid;
    idx = (visited * 32) + nodeid;
    if (visitCache[idx]) {
      return visitCache[idx];
    }
    var neighbours = nodes[nodeid];
    var max = 0
    for(var i=0;i<neighbours.length;i++) {
      if (!(visited & (1 << neighbours[i].dst))) {
        var dist = neighbours[i].cost + getLongestPathCached(nodes, neighbours[i].dst, visited, depth+1);
        if (dist > max) {
          max = dist
        }
      }
    }
    visitCache[idx] = max;
    return max;
  }