Factoring Cartesian bitwise join of bit vectors
Passing to the dual hypergraphs to look for products.

As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.


Vertices are the elements of $[n]$; 
An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x_v = 1$.


(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where


The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and
A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x_e =1$;


&mdash; that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge".
This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H_C$ obtained from a multiset $C$ now has a composite number of vertices $m$:  we would like hypergraphs $H_A$ and $H_B$ such that $V(H_C)$ has some particular bijective correspondance with $V(H_A) \times V(H_B)$.

A diagonally restricted tensor product of hypergraphs.

Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.)  The Cartesian bit-wise meet condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H_A) \times V(H_B) \to V(H_C)$$ such that the edge labelled $e \in [n]$ in $H_C$ contains only the vertices $\varphi(a,b) \in V(H_C)$ such that both $a \in V(H_A)$ and $b \in V(H_B)$ are contained in the respective edges labelled by $e$ in $H_A$ and $H_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.


If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the tensor product of graphs, also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H_A) \times E(H_B)$ which contain all vertices $(a,b) \in V(H_A) \times V(H_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H_A \otimes H_B$.
To re-obtain the Cartesian bit-wise join of $H_A$ and $H_B$, we must 
restrict to the diagonal edges $(e,e) \in E(H_A) \times E(H_B) =
   [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H_A$ and $H_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are searching for hypergraphs $H_A$ and $H_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.


The resulting reformualtion.

From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:


  Is an edge-labelled hypergraph $H_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (i.e. taking only the diagonally labelled edges) of the tensor product $H_A \otimes H_B$ of two labelled hypergraphs $H_A$ and $H_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?


I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.