You're right, it is virtually impossible to remove IE from Windows.
However, it is possible (in theory), but causes a lot of problems.
I think he may have looked further than just his desktop for a browser.
If he hasn't got it/can't find it, the easiest solution is probably to just put Firefox on a flash drive and install it.
Alternatively, either of fffreak's suggestions should work.