I write lots of modules which look like this:

function get(index, callback) {
    if (cache[index] === null) {
        request(index, callback); // Queries database to get data.
    } else {
        callback(cache[index]);
    }
}

Note: it's a bit simplified version of my actual code.

That Callback is either called in the same execution or some time later. This means users of the module aren't sure which code is run first.

My observation is that such module reintroduces some problems of the multi-threading which was previously solved by JavaScript engine.

Question: should I use process.nextTick or ensure it's safe for the callback to be called outside the module?

It depends entirely on what you do in the callback function. If you need to be sure the callback hasn't fired yet when get returns, you will need the process.nextTick flow; in many cases you don't care when the callback fires, so you don't need to delay its execution. It is impossible to give a definitive answer that will apply in all situations; it should be safe to always defer the callback to the next tick, but it will probably be a bit less efficient that way, so it is a tradeoff.

The only situation I can think of where you will need to defer the callback for the next tick is if you actually need to set something up for it after the call to get but before the call to callback. This is perhaps a rare situation that also might indicate a need for improvement in the actual control flow; you should not be rely at all on when exactly your callback is called, so whatever environment it uses should already be set up at the point where get is called.

There are situations in event-based control flow (as opposed to callback-based), where you might need to defer the actual event firing. For example:

function doSomething() {
    var emitter = new EventEmitter();
    cached = findCachedResultSomehow();
    if (cached) {
        process.nextTick(function() {
            emitter.emit('done', cached);
        });
    } else {
        asyncGetResult(function(result) {
            emitter.emit('done', result);
        });
    }
    return emitter;
}

In this case, you will need to defer the emit in the case of a cached value, because otherwise the event will be emitted before the caller of doSomething has had the chance to attach a listener. You don't generally have this consideration when using callbacks.