I think this new law is great and should already have exist earlier.
This sentence doesn’t seem correct to me. I don't know what, but something is disturbing me. Is it the tense of some verb? Or a false construction?
You're right, there is a tense problem. "Should already have exist" should be "should already have existed." This is the past progressive (or past continuous) tense combined with a modal verb "should." The auxiliary "have" cannot be combined with the present tense form of a verb: it always takes a past participle.
A more idiomatic way to say the same thing is:
I think this new law is great and should have been passed earlier!
But the original version is grammatical when "exist" is corrected to "existed."