(Note I'm answering my own question in Q&A style since I thought this would be neat to share.)
In order to explain this properly, I have to go into a bit of grammar first, including Old Japanese, but towards the end it'll be clear how it all connects.
So in English, we form to-be sentences like "This is an apple." The structure of this sentence is S V C, or subject (this) verb (is) complement (an apple). This isn't the same as S V O (subject verb object), because for technical reasons, "is" takes a complement and not an object.
In modern Japanese, there is a similar phenomena. In the sentence 私は先生である ("I am a teacher"), you can actually pick out a subject, verb, and complement. The subject is 私は (I), which also functions as the topic, the complement is 先生で (a teacher), and the verb is ある (am / exists). You might say that the verb is not ある but である, but if you think about it, である is very unlike other verbs because it attaches directly to a noun, while other verbs require the noun to have a particle. This is actually because the particle で is built into the verb である, so really で is the word that attaches to the noun and ある is the verb at the end of the sentence. This also explains why you can say ではある or でさえある with a particle between で and ある.
In Old Japanese, the situation was very similar, except that instead of である, you had にあり. に was used instead of で, and ある conjugated irregularly with a sentence final form of あり. にあり was more commonly said as なり, which is just a contraction of the sounds. So a sentence like 私は先生なり would be the old Japanese equivalent of 私は先生である (albeit with modern vocabulary). Grammatically, the subject of this sentence is 私は, the complement is 先生に, and the verb is あり.
Now, what about a statement like, "I am a teacher. But he is not." If we look closely, the grammatical breakdown is "S V C. But S V-negative." The complement (a teacher) completely disappeared from the second sentence because it's clear from context. "I am a teacher. But he is not a teacher," would also be grammatical, but it sounds wordy / redundant with the complement included.
In modern Japanese, the same statement (I am a teacher. But he is not.) can be rendered 私は先生である。けれど、彼は先生ではない, but notice that we repeat the word 先生 twice. This doesn't grate on Japanese ears as much as it does on English ones, but we could avoid repetition if instead we said 私は先生である。けれど、彼はそうではない. In both of these cases, the sentence structure is "S C V. But S C V-negative." Notice that unlike English, we cannot eliminate the complement (先生で / そうで). We could attempt to say けれど、彼はない, but this would simply be misinterpreted because it is unusual to omit the NOUNで part of NOUNである.
However, in Old Japanese, it was completely possible to omit the NOUNに part of NOUNにあり. So, the sentence can be rendered 私は先生なり。されど、彼はあらず (あらず is the negative of あり). Notice that we don't have to say 彼は先生にあらず and can omit the 先生に part completely. The structure of this sentence is thus "S C V. But S V-negative." This can be equated with the English structure, which was "S V C. But S V-negative." Notice that the second sentence of both English and Old Japanese has the same structure.
So, in Old Japanese, あり / あらず could mean "is (so)" / "is not", functioning as NOUNにあり / NOUNにあらず with the NOUNに part omitted due to it being clear from context.
For the sake of giving a "native" example written by someone from the era, here is a quote from Makura no Soushi:
「翁丸(おきなまろ)か」とだに言へば、よろこびてまうで来るものを、呼べど寄り来ず。あらぬなめり」（「翁丸か」とさえ言えば、（いつもは）よろこんでやってくるのに、呼んでも寄って来ない。翁丸じゃないようだ。）
"If I just said, 'Is it you, Okinamaro? (dog's name)' he would come happily to me. But yet, although I call him, he does not come near. (I thought it was him, but) It would seem it isn't."
In this case, あらぬ (attributive form of あらず) stands for 翁丸にあらぬ / 翁丸ならぬ "It isn't Okinamaro." So in essence, あらず would mean それじゃない / そうじゃない in modern Japanese.
This usage of あらず further evolved to mean "it isn't it" "it's different", and could be used before nouns as あらぬ to mean "a different" "another".
Again from Makura no Soushi:
「則隆(のりたか)なめりとて、見やりたれば、あらぬ顔なり」（則隆だろうと思って、見やったら、違う顔だった）
"When I turned to look, thinking it must be Noritaka, it was a different face."
So, through this process, あらぬNOUN came to mean "a different NOUN", and thus あらぬ方向 came to mean "a different direction".
Sources: Japanese examples and the etymology of あらぬ are from 古典文法総覧 by 小田 勝. Modern translations, English and Japanese, are originals of mine, but I release them to the public domain and welcome anyone to edit / improve them.
