На мой взгляд вполне законно можно уволить, просто надо соблюсти формальности:
Оформить докладную записку, акт и табель соответствующим образом. Например http://online-buhuchet.ru/neyavka-na-rabotu-progul/ описано что и как. Какая разница что свидетели прогула не работают в организации, разве что-то в законах об этом сказано? И вообще, увольняется же человек не по судебному решению.

Другое дело что работник вполне законно может опротестовать увольнение в суде и даже выиграть, поскольку как Mmartina говорила - свидетельство работников сторонней организации судом может воспримется критически. А может и не выиграть. А может и в суд работник не подаст.