"It doesn't always X" vs "It always doesn't X"

Solution 1:

Your intuitions are correct. They do mean different things.

The particular difference is predictable from the relative positions
of the negative don't and the universal temporal quantifier always in the propositions.
There are two possible positions.

1. The negative can include the quantifier in its scope
   Job interviews don't always go well, in logical terms
   NOT (ALWAYS (Go-Well (Job-Interviews)))

2. The quantifier can include the negative in its scope
   Job interviews always don't go well, in logical terms
   ALWAYS (NOT (Go-Well (Job-Interviews)))

Quantifiers, Negatives, and Modals are all logical operators and have very complex interactions.
In particular, any clause with two of them is potentially ambiguous, unless it's compositional,
like your examples. See The Logic Guide for further information.

Solution 2:

You are correct. The I don't always meme, which has many fine examples, does indeed affirm this.

The technical reason, if you want one, comes intuitively if we consider the order of operations, given by the positioning of the words within the clause they form.

Taking your sentences as you gave them, then:

Job interviews don't always go well.

In this sentence, always is applied to the act of 'going well', and don't is subsequently applied to always, with the effect of negating it. In set theory terms, in the complete set of all job interviews ever conducted (or to be conducted), it is not true that they all will go well. In other words, at least one of them won't.

This phrasing is very common, although depending on the ratio of job interviews going well versus not going well, one might substitute 'don't always' for something that indicates the broad probability of the success of job interviews - such as rarely, sometimes, or often.

Job interviews always don't go well.

In this sentence however, the inversion of don't and always radically changes the logical proposition indicated by the phrase. Here, don't is applied to negate the act of 'going well', and always is applied to to don't, making this negation universal. In set theory terms, in the complete set of all job interviews ever conducted (or to be conducted), it is true that they will all not go well.

This phrasing, however, is less common - always don't would much more naturally be substituted for never, a perfect word for assigning the condition of always being false.