So, I recently learned that 并未 is a formal way of saying 并没有. However, whenever I see it in writing it is always paired with a two word set. (i.e. 并未解决， 并未提出， 等。 ） Is this a hard and fast rule? I've noted that when pairs of two words are put together it indicates that it is relatively formal. Is 并未 too formal for spoken or common written language?
You are right about
并未 being formal, but there are cases where it can go with one word.
I just made this one up, but it sounds perfectly fine.
The reason that you only see it paired with two words is simply because modern Chinese words are often used in the combination with others. Totally the opposite in old days though, that's why the sentence above is OK, it's more like old way of writing.
Is it too formal for spoken language? Yes.
Is it too formal for common written language? No.
Your observation is correct. 并未 is formal and sounds natural only when it's followed by a two-character word (to clarify, these are not two-word sets).
It does sound too formal to use in spoken language and common/casual writing. You may want to use 并没有 in your diary or blog.
As for why it doesn't sound natural to pair 并未 with 1-character or 3-character words, I don't believe there is a simple grammatical rule. Linguists tend to explain that using either word formation or prosody rules. Common folks would attribute that to idioms and language sense.