The sort key for most category collations other than "identity" or "uppercase" currently depends on which PHP or HHVM version is in use, not just on which ICU version is in use. Here is an explanation.
MediaWiki relies on the Collator::getSortKey() function provided by PHP's intl extension, a binding to the ICU library. The function was added by PHP developer @Smalyshev and is available since 5.3.2 (php/php-src@65c1421). Until 5.3.15 and 5.4.5, PHP Bug #62070 caused a "String is not zero-terminated" warning in debug builds. (Until rMW8fc4dea67935fb0f, MediaWiki worked around this bug by appending the empty string while suppressing warnings.)
However, the bug was fixed not by increasing the buffer size by one byte and manually terminating the string, but rather by returning a string length one byte shorter than before, relying on the fact that to allow comparison using strcmp(), all sort keys end with a null terminator byte. This is a backwards incompatible change that affects comparisons to sort keys stored in the database, when multiple pages have the same sort key.
Whether PHP should include the null byte or not is unclear. Though PHP generally does not count a null terminator as part of a string's length or make it user-accessible, ICU documentation includes a hex "00" at the end of each example sort key. And while PyICU (for Python) does include the null byte in the binary string it returns, Unicode::ICU::Collator (for Perl) does not. So I decided it would be better not to break backwards compatibility a second time, and instead file PHP Doc Bug #72271 and HHVM Issue #7106. An HHVM patch to make behavior consistent with recent PHP versions was proposed, then merged on May 31 (facebook/hhvm@b049baa).
MediaWiki should choose one or the other though. It could follow what recent versions of PHP do, by stripping off the null byte if there is one, so we don't have to keep the workaround forever. This would also minimize the impact on those who have already upgraded to PHP 5.5 or newer. However, Wikimedia runs HHVM, so would have to fix their sort keys. A temporary migration flag could be added for Wikimedia's use, and turned off only once Wikimedia is ready to do the migration.