  An orthogonal product basis of a composite Hilbert space is genuinely
nonlocal if the basis states are locally indistinguishable across every
bipartition. From an operational point of view such a basis corresponds to a
separable measurement that cannot be implemented by local operations and
classical communication (LOCC) unless all the parties come together in a single
location. In this work we classify genuinely nonlocal product bases into
different categories. Our classification is based on state elimination property
of the set via orthogonality-preserving measurements when all the parties are
spatially separated or different subsets of the parties come together. We then
study local state discrimination protocols for several such bases with
additional entangled resources shared among the parties. Apart from consuming
less entanglement than teleportation based schemes our protocols indicate
operational significance of the proposed classification and exhibit nontrivial
use of genuine entanglement in local state discrimination problem.
