This type of "unsual" word order is often called scrambling. This term includes when modifiers are detached from what they modify (or vice versa) and where grammatical heads and their complements are displaced from their "expected" positions. How much scrambling languages allow depends on the language, the genre, and the type of scrambling. Even English has scrambling, but not to the degree allowed in Latin.
From what Devine and Stephens say in their books on word order and discontinuous syntax, there seems to have been a definite difference between Latin poetry and prose in terms of how much and what type of scrambling was acceptable. There was also a variation over time between Cato the Elder (234–149 BC) and Livy (4/59 BC – AD 12/17).
The fact that the genre and time period are relevant in understanding how much scrambling was acceptable suggests that spoken Latin would also have had less scrambling than written Latin, but that what was acceptable would also have varied with time.
Scrambling in itself is apparently not unusual in certain types of languages, particular in those classified as non-configurational. Surprisingly, the ones I have read most about have only oral traditions, strongly suggesting that scrambling is not an artifact of written language. These languages heavily disfavor or forbid dependent relationships between words, and therefore individual words have more independence with respect to word order. This is similar to what is allowed for prepositional phrases in English, which generally have great freedom in word order.
The languages that do have extensive scrambling accomplish this by a relatively heavy reliance on head marking, dependency marking, cross-referencing, and paratactic arrangement of words.
Based on what Devine and Stephens say in their books, I think that the phrase you cited in your question, "tarda solet [magnis] rebus inesse fides," is not of a type that would have been particularly unusual in oral Latin language, especially in older time periods. However, it does strike me as having a certain style that is more normal for maxims, which usually contain more archaic styles of speech. Delaying the word "fides" till the end seems to signal that it is "tail" material and therefore already given information in terms of the discussion, even though the maxim itself would be removed from the normal flow of conversation. In other words, the maxim, in using this order, signals that something about how faith works has already come into the conversation that the listener should reflect upon.
The type of scrambling that would not occur in oral Latin would be scrambling representing obsolete stages of Latin. I can't remember examples from Latin, but I think Devine and Stephens say that scrambling adjectives out of prepositional phrases before the preposition was limited to verse in Ancient Greek, such as in θοὰς ἐπὶ νῆας (swift, unto the ships)(Homer's Iliad 1.12. It appears fairly frequently in Homer, which we believe to have originally been orally performed poetry. The paratactical style of the language also comes across quite strongly in Homer, where clause after clause are often linked with particles that do not signal a syntactic dependency, but only a semantic one.
I also think that Latin verse uses specific effects that were probably absent in normal speech, such as using interlocking adjective-noun phrases: saevae memorem Iunonis ob iram (Virgil, Aeneid, 1.5)
"on account of the mindful anger (memorem iram) of cruel Juno (saevae Iunonis)". Or using the scrambling to mimic real world actions, such as in
quis multa gracilis te puer in rosa (Horace, Odes, 1.5) "what graceful boy (gracilis puer) (is embracing) you (te) amidst many a rose (multa rosa)?", where the words referring to the boy and the roses embrace the word referring to the girl.