Before I move on to the topic, here is my analysis based on my grammar book:
The bolded part are quotation (引用), and the と behaves as a 格助詞 (quotation particle).
The bolded part are adverbial phrases.
Following this logic, I conclude that
これを嘘だと思う。 →quotation (引用)
これを嘘と思う。 →adverbial phrases
Hopefully someone could comment on my analysis, and more importantly, the difference of their usage. I mean, the situation when the two sentences are not interchangeable. One Japanese told me that the two sentences have little difference and can be used interchangeably, but I wonder if there is any exception.
Feel free to add more/change words to make the sentence sound more natural, 違和感がない. For instence, 「それをうそと思うかはあなた次第だ」
"当然のことと思う"/"当然のことだと思う" is another pair where I have the same question.