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.