Complexity of a matrix problem
Well, here's a not-horrible upper bound over $\mathbb{C}$: $\mathsf{PSPACE}$, or assuming the Riemann Hypothesis, $\mathsf{AM}$. This is because for any given patterns of zeros for $A,B$, checking whether one can make $AB=I_n$ is checking whether a certain system of $n^2$ integer polynomial equations has a solution in $\mathbb{C}$, and this can be done in these upper bounds, by Koiran.

Another approach is to try to leverage the fact that this is in fact a system of bilinear equations. Solving bilinear equations is equivalent to finding "rank 1" solutions to linear equations. I've been trying to determine if there are better upper bounds for solving bilinear systems in general, but with no luck so far. It's also possible that one could leverage the particular structure of these bilinear equations to get something better than what's known in general...