I watched the early ones again recently myself and I agree with StudentCarl. There were some competent groundfighters in the early UFCs but they still could not deal with Gracie's BJJ. Taking your example of Frank Shamrock, he fought Royce Gracie at UFC 1 and was submitted in 57 seconds. I don't consider that "dealing" with Gracie BJJ. You can watch a
video of that fight.
In fact if you look at it his first 10 fights in the UFC they finished at 2:11, 0:57, 1:44, 5:08, 1:07, 1:31, 1:17, 4:40, 3:59 and 5:32. Only two of his first 10 fights went outside what would be called the first round in modern UFC. That hardly seems like the fighters knew how to deal with his style.
I think StudentCarl's (widely held) opinion is a lot more fact than myth.