Se puede jugar con la función según cómo se vayan a usar los textos, lo cual tú conocerás mejor que nadie. Por ejemplo, si sabes que los textos van a estar bien escritos, puedes usar dos veces la función:
Código PHP:
$texto = str_replace( " al ", " EL ", $cadena );
$final = str_replace( "Al ", "EL ", $texto );
Así sólo sustituirá "al" cuando sea una palabra intermedia (un espacio antes y después de "al") o cuando esté al comienzo de una frase, empezando por mayúscula y terminando en espacio porque acaba la palabra.
Otra opción sería añadir " al." por si termina en esta palabra, pero no tiene sentido que algo termine así.