I'm wondering if "tre" and "multe" are interchangeable in every situation, is there a rule that decides which one to use?

mi dankas vin pro vian tempo kaj helpo

As far as I'm aware, they are indeed interchangeable (at least all the times I've seen them used thus far)

Ŝi estas tre bela virino; li estas tre inteligenta homo

I would be strange to use multe in the above.

Mi ne havas multe da mono. It would be strange to say tre. But Mi ne havas tre multe da mono would be OK

mi dankas vin pro vian tempo kaj helpo

pro via ...no accusative

As Sudanglo already hinted, they are generally not interchangeable.

Tre is a particle with the sense of "in high degree" and it is used
 
1. before an adjective or an adverb to express absolute superlative

      Ni devas esti tre singardaj en tiaj okazoj (Z) : We must be very careful in such cases.

2. before a verb to express intensity of the action

      Vi devas rakontadi al mi historiojn, ĉar mi tion tre amas (Z) : You must tell me stories, because I greatly love/very much like them.

      Mi tre dankas : I am very grateful.

Multe is an adverb created from the adjective multa. The adverb is used (numbers refer to PIV)

I-1 to show that an action lasts long or gets repeated

      Kiu multe parolas, ne multe faras (Z) : Who speaks a lot, does not do a lot.

I-2 to show that an action concerns a great quantity or is relative intense

      Vundo sekreta doloras plej multe (Z) : An invisible wound hurts most.

I-3 to emphasize comparison

      Ĝi flugis multe antaŭ ĉiuj aliaj (Z) : It flew far ahead of all others.

II like a noun to show a great amount

      Kiu tro multe deziras, nenion akiras (Z) : Who wants too much, gets nothing.

To summarise multe as an adverb is used to modify or emphasize the action or used indepently to show a great amount, while tre as a particle is mostly used before an adjective or an adverb. Where they can be considered to overlap, is when tre is used with a verb, but even then multe is about amount and tre about intensity.