Why is 他从商店出去了 correct but 他出商店去了 incorrect? 他出商店去了。
他从商店出去了。 


Why is only the second sentence right? I knew that when we use a directional complement, we could put the object in the middle between the two verbs. So why do I have to use 从 in this sentence to make it grammatically correct?
出 and 去 are both verbs, you can't use both as separate entities. 出去 on the other hand is a resultative verb, you can't break it up.

从 (from) is here a preposition indicating direction.

A similar expression would be 他到哪儿去了, where 到 (where/to) is the corresponding preposition.