Which is correct: 已经毕业了两年大学 or 已经大学毕业了两年? I know 大学毕业 is a verb phrase that means "graduate from university". I have 2 questions.

(1) In expressing the duration of completed action, which is correct: 他已经毕业了两年大学  or 他已经大学毕业了两年?

(2) If I change the word order, is it still grammatically correct: 他大学毕业已经两年了?
The verb phrase is "大学毕业" 

Following the rule of verb particle 了 must be placed after a verb or verb phrase, the following are both correct

[已经][大学毕业][了][两年] (了 is a verb particle )

[大学毕业][已经][两年][了] (了 can be a verb particle or a final particle)

Since 大学毕业 is [n + v] not [v + n], you cannot insert the verb particle 了 between verb and noun. e.g. 读完大学 --> 读完了大学. 

We can say 吃饭  but not 毕业大学 because 吃 is a transitive verb (take object), but 毕业 is an intransitive verb (doesn't take object)

毕业大学 is not grammatical, therefore 毕业了大学 is also not grammatical.