I already posted my question on Stackoverflow:
The problem appears when I try to use the results of the Stored functions in the ORDER BY. I also tried to store the result (without the ORDER BY) in to a temporary table, but ended up with the same result. The query runs fast if I remove the ORDER BY.
Any directions are very welcome, thanks!