This is a very, very difficult area to give guarantees on, especially in the environment you are discussing.
As you suspect, deleting the history doesn't wipe all details. This link here discusses the perils of Internet Explorer's index.dat file. It also suggests that Firefox does something similar.
Also, remember that deleted files can be undeleted as well. Depending on how forensic the person looking for this info wants to get, more and more tools are at their disposal. Also, even it can be wiped clean, this could be the sort of situation where the absence of a history is deemed enough of a problem. If someone is going through the browser history and finds that it has been deleted, that might trigger the reaction that whoever deleted the history is trying to hide something, with horrible consequences.
Finally, watch out for any keyloggers installed. These could sniff and record any keystrtokes and store them for later retreival. This could be a hardware or software deal.
Any PC running any software is prone to revealing what you've been up to. The ideal solution (though maybe not practical in this situation) is to use public computers.