Changes have been made in Git (master):

commit e02440a4ad7932b0c02437e602005b9522d0478d
Author: Jan Schneider <jan@horde.org>
Date:   Thu Apr 7 15:21:34 2016 +0200

     Add a test for bug #14318.

  .../test/Horde/Css/Parser/ParserTest.php           |    8 ++++++++
  1 files changed, 8 insertions(+), 0 deletions(-)

http://github.com/horde/horde/commit/e02440a4ad7932b0c02437e602005b9522d0478d

Thank you!

Changes have been made in Git (master):

commit c462001168dc27dc786d9dacf244feb06cf33087
Author: Jan Schneider <jan@horde.org>
Date:   Thu Apr 7 15:16:51 2016 +0200

     [jan] Fix upstream regression causing infite loops with empty CSS 
documents (Bug #14318).

  framework/Css_Parser/lib/Horde/Css/Parser.php |    5 +++++
  framework/Css_Parser/package.xml              |    4 ++--
  2 files changed, 7 insertions(+), 2 deletions(-)

http://github.com/horde/horde/commit/c462001168dc27dc786d9dacf244feb06cf33087

Sorry but i don't know what you mean. The bug is present as i described it.

This empty style tag is already stripped off here. Probably through tidy.

Also this helps (but don't forget to remove 3 characters somewhere from body):
<!--a75c305b1c0a6022--><style type="text/css">aaa</style>

The problem is with empty <!--a75c305b1c0a6022--><style> tag.

I tried to replace this:
<!--a75c305b1c0a6022--><style type="text/css"></style>

with this (so message size will remain the same):
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

and problem was gone for this message.

Debian Wheezy, PHP 5.6.20 (from dotdeb.org), all Horde packages on 
newest stable versions.

I'm able to 100% reproduce it with that message. This is related to CSS:
<!--a75c305b1c0a6022--><style type="text/css"></style>

Still cannot reproduce and it wouldn't have made any sense anyway, 
since the message didn't contain any CSS at all.

Got it! Pls remove it from ticket after you download it, thank you.

Any idea how to find such a message? It was triggered by our users 
(who probably doesn't know that something like this happened).

Can you provide an example (HTML) message that triggers this?

See also Ticket: 14317

After upgrade to 1.0.9, Horde_CSS_Parser started to take 100% CPU in 
some cases and possibly causing a DoS (when max_execution_time is 
disabled):

2016-04-06T14:23:09+02:00 EMERG: HORDE [imp] Maximum execution time of
120 seconds exceeded [pid 20629 on line 578 of
"/usr/share/php/Horde/Css/Parser/vendor/sabberworm/php-css-parser/lib/Sabberworm/CSS/Parser.php"]

2016-04-06T14:23:08+02:00 EMERG: HORDE [imp] Maximum execution time of
120 seconds exceeded [pid 20617 on line 18 of
"/usr/share/php/Horde/Css/Parser/vendor/sabberworm/php-css-parser/lib/Sabberworm/CSS/Parsing/UnexpectedTokenException.php"]

  2016-04-06T14:34:29+02:00 EMERG: HORDE [imp] Maximum execution time of
120 seconds exceeded [pid 7743 on line 96 of
"/usr/share/php/Horde/Css/Parser/vendor/sabberworm/php-css-parser/lib/Sabberworm/CSS/Parser.php"]

Downgrading to 1.0.8 seems to fix the problem.