It reminds me of: http://www.phpbb.com/bugs/phpbb3/25235
the problem is, mnessage subject is not shortend by truncate_string() as post_subject and topic_title are.

Fix should be something like:
includes/functions_privmsg.php

	// Recipient Information

	$recipients = $to = $bcc = array();

after add:

	// First of all make sure the subject are having the correct length.

	// To achieve this without cutting off between special chars we convert to an array and then count the elements.

	$subject = truncate_string($subject);

The same problem occures while saving drafts of PMs and Posts.

Also the problem wasn't fixed completely, as it still occures, while replying to a topic.
this is caused by

	if ($strip_reply)

	{

		$string = 'Re: ' . $string;

	}

which is added to the 255 chars after checking for the length.
the fix for this behaviour is:
includes/functions_content.php

while (utf8_strlen($string) > $max_store_length || !sizeof($chars));

replace with:

while (utf8_strlen($string) > (($strip_reply) ? ($max_store_length - 4) : $max_store_length) || !sizeof($chars));

the same problem may occure with $append, just didn't find a place where it is used

While i was asking some points about this in the #phpbb-qa fawek confirmed this bug in the ACP and UCP