locate php выдаёт огромнейший список всего под ряд =)
which php5 вообще ничего не выводит
whereis php5 вывел несколько путей, но по ним только конфиги и разные библиотеки.

А может быть такое что самого бинарника нет, а выполняются на веб-сервере скрипты через so-библиотеку?