Data Sphere

How long have we been fighting the CA on Paradiso, or just in general, and when did the Tohaa show up?

The way the Paradiso book is written makes it hard to tell. There is no time table to follow. Which year are we in in the Infinity universe anyway? Does CB move the time forward? I am not so sure.
There are some wars which are described to be in the past, and the Paradiso conflict is the present. All references to time I could find are rather vague. I guess that CB does this intentionally.

But we don't even have a rough idea? I'm trying to write a bit of fiction, and the timing of the war is kind of important to it.

you find info on this in the back of the N3 Background book and of course, the Paradiso book. I tried to find years, but there was virtually nothing. All I know is that the Neocorporate Wars ended more than 10 years ago. Surprisingly little.

Well, according to the timeline published in the Bibliotekfiles Ezine (the early CB webzine), the First Neocolonial War was in 2170, and the Last Neocolonial War was in ~2173. Ariadna was rediscovered about 2175, and the war with the Combined Army on Paradiso started roughly 2182. The timeline in the Ezine stops about 2185, and that was the time of the Core Book.

My guess is that the Tohaa showed up 3-5 years after the start of the Paradiso Conflict, but it's been a year or two since then.

It could be 2191 (2016+175=2191), if we take the 175 years into the future literally.

Technically speaking, the Tohaa showed up (in the fluff) prior to the "accident" that lead to the collapse of the wormhole stranding the Ariadna on Dawn (and they were directly responsible for the diversion of the Aurora (Dawn ship 2) to paradiso). Since it was their playing with the wormhole tech that lead to those issues.