So I recently found out I'm not sure when to use ます form. Not like in general, but rather within sentences.

Like for instance:

A: そんなことははないと思います
vs
B: そんなことはありませんと思います

or

A: 車が壊れたから仕事に行きませんでした
vs
B: 車が壊れましたから仕事に行きませんでした

Are both A and B valid? Is B just more formal sounding than A? Is it OK just to do ます for the last verb in the sentence?

I'm not an expert but I think you can't use ます form before と思います/思う.
The second example is more tricky but I think generally tense&politeness is expressed at the end of a sentence and often putting ます/other polite forms before that is ungrammatical and incorrect.

Generally, ます forms within sentences are found only in very formal speech or some kinds of writing. This is definitely true of ましたら. ます + と思います I'm not sure about; it's definitely rare but it might show up in very formal usage as well.

As a general rule you should only use ます at the end of a sentence.

Sweet, that totally makes sense. For some reason for a long time I thought it was all ます or nothing. Maybe because I don't see ます that frequently in the stuff I read...

If you're reading stuff you would tend to find it only in dialogue since it's not used in most narrative writing or non-fiction. It's pretty much a feature of spoken Japanese; you only see it in writing when the author is trying to inject a personal, spoken feel to the writing (and often not even then).

The use of ます forms inside sentences that usually take the dictionary for like in ~ましたら is rather common in formal speech. You can hear it if you talk to the staff in departmental stores, who in general tend to use an overly polite language. The combination ますと思います is possible in theory but for real nobody would say so, because the part of と思います implies that the speaker is communicating his/her thoughts and in the context of politeness where the ます forms are emphasized, the speaker rarely expresses his/her thoughts. At most, they would use でしょう instead. In your example, そんなことはありませんと思います, it would be in a real case as そういったことはございませんでしょう。

Maybe the most common use of ます forms for emphasizing politeness would be in the て form and together with ので

その件につきまして、私には答えかねます。　　(Usually it would be その件について)

この辺では、盗難の恐れがありますので、ご注意ください。　(Usually it would be 恐れがあるので)

In conclusion: Although you will find these expressions WRITTEN and sometimes spoken, they are NOT part of the regular way of speaking and you will sound rather weird if you use them in everyday conversation.

Basically, the big dividing line between a polite way of speaking and a casual way of speaking is whether the final verb in the sentence is in ます forum. The rest of the verbs are generally done in dictionary form.

You will hear people use ます within a sentence, but usually it's when speaking　敬語.　 Non-native speakers of Japanese are basically never in situations where they have to use very over-the-top honorifics, so as a non-native speaker you only need to understand it, not speak it. (Basically this is because the types of jobs that non-native speakers work in are limited)

I definitely hear older women in Kyoto use ~ますと思います, but I have no idea to what extent it's considered standard. (Over the years I've gradually accepted that the ます form can be used almost everywhere if the speech is polite enough, but some ways of using it are more standard than others) A lot of times it seems like the と思います is an afterthought. They were going to end their sentences with the first ます verb, but then they suddenly realize that it would be best to soften it a bit more by adding that it's just a thought, so they throw in a と思います.

車が壊れましたから仕事に行きませんでした is much more common than そんなことはありませんと思います, because the former sounds like two sentences: 「車が壊れました。」 and 「仕事に行きませんでした。」 Because of that it's pretty common to use ます form before　から and similar sentence connectors.

I see ~ます/~です　creep up a lot in the middle of sentences that use "but" phrases. That is, before が、けど、けれども etc