"This is usually one of the first things I tell just to ensure the cause of the
(compatibility) problem can be found faster."
What actually happens is they refuse to continue until you try the Windows platform solution.
If you don't tell them it's Linux, they assume it is Windows and the question never arises.
The likelihood that they have problems with Windows/MAC uses it usually quite high too.
You can then provide something which you magically got to work and they thank you for getting them out of the situation.
"I never accept a job if they don't allow me to use Ubuntu."
You are braver than me.
I'd rather avoid the issue until contracts are signed and I'm onsite.
It's harder to back out of a contract than not to sign in the first place.
"If I tell them first and have it as a precondition to even start
working there, I have more arguments that they need to at least
provide the minimum required environment to use Thunderbird for
example (e.g. activating the IMAP service at the Microsoft Exchange
This is the utopian view, but I find that clients will simply move to the next CV.
Most exchange servers now have web access enabled so employees can work from home.
This means support is not an issue for email, LibreOffice will do a pretty good job of interfacing with Microsoft Office stuff and you can CIFS mount the windows shares.
I find it is better basically not to tell anyone you are using Linux until you either have to (for support/request reasons) or after you have been working on the clients project awhile (like a month) and then reveal it.
Once you have established that it is not a hindrance to the project and working relationship they are more likely to just let you get on with it.
To tell them beforehand sets all sorts of bells ringing (for the wrong reasons) and then you become the "problem" with your weirdo software.
I have worked with 10+ clients onsite on their internal networks since I started to use Linux and I have a 100% hit rate this way.
Trust me, I do ensure they know I'm using Linux and let them find out why as the working relationship progresses, but I'm careful to ensure it is introduced the right way and the FUD is seen for what it is.