Eu estava testando outras coisas e constatei que não funciona mesmo com o urldecode.
Na verdade não poderia ser esse o problema pois se não, ele não conseguiria substituir no str_replace os espaços por underlines, pois na url codificada, os espaços tambéem são codificados

Você imagina o que mais possa ser?
Alguém pode me ajudar?!
Alguém poderia por favor me ajudar com isso?!?!

????????????????????????