The notion of a "witness" is that it is a measure which will not give a false positive. That is:
If witness reports there is entanglement, then there is (assuming the
experiment has not gone wrong in some way).
If witness does not report there is entanglement, then there may or may not be entanglement present.
The study of entanglement witnesses is itself quite complex, so it's hard to answer your further questions. It depends on the scenario. In the standard Bell state case, you have a pair of particles and you want to know whether or not they are in a product state. I think that if you only have access to one copy of a pair of particles in some given state, it won't be possible to determine whether or not they are entangled, because for each entangled state $|\psi\rangle$, there are product states $| u \rangle$ such that $\langle u | \psi \rangle \ne 0$, so there is always a product state which can partially 'mimic' an entangled state.