From what I understand, if I have a function CMP("a", "b") that returns the sort order of "a" and "b" that function cannot be marked as IMMUTABLE, because a change to the collation may change its output (since the sort order of those two characters may have changed)
IMMUTABLE functions need to be IMMUTABLE across database versions, too.
Or at least, in MySQL, they do (I forget how mysql marks immutable procedures)
From gitter: