<p>Our company is sending out a lot of emails per day and planning to send even more in future. (thousands) Also there are mass mailouts as well in the ten thousands every now and then.</p>

<p>Anybody has experience with hotmail, yahoo (web.de, gmx.net) and similar webmail companies blocking your emails because "too many from the same source in a period of time" have been sent to them?</p>

<p>What can be done about it? Spreading email mailouts over a whole day/night? At what rate?</p>

<p>(we are talking about legal emailing just to make sure...)</p>

If you want to do this you're getting into some of the same techniques spammers use. Spreading email mailouts over a day or night could be a way to do it. I don't think anyone  knows the 'right' rate to do this because varies per mail-provider and they probably adjust this over time. You could try spreading the emails sent to a single provider. If you've got a lot of mail for hotmail.com for example then don't send it all at the same time.
Maybe it would be a good idea to look at pull media instead of push media for your application. You could put the content of the mass mailings up on a website and notify interested readers with an rss feed for example. This has a lower risk of irritating potential customer. And your company has a lower risk of being sued for spamming.
You're right, rss is not really accessible for all users. But as you'll probably need to create a webpage-alternative to the mailings anyway for people who can't read html-mail. You might as well provide an rss feed to those pages as an alternative for the users who do want to use it. This might reduce the volumes for the mailings enough to make your job a bit easier.