For efficient heuristics I'd suggest looking into the CAD literature on the state encoding problem (assigning binary identifiers to states of a DFA to minimize the amount of logic for the state transition function.) Devadas and Newton, "Decomposition and factorization of sequential finite state machines," IEEE TCAD, 8(11):1206-1217, 1989 points out that there is a close relationship between state encoding and state machine decomposition.
If for a DFA with $N$ states you assign a unique $M$ bit state identifier to each state ($\lg_2N < M\leq N$), then you have essentially decomposed the DFA into a network of $M$ interacting two-state machines. Equivalently: you have defined a set $S$ with $M$ elements, and assigned a unique subset of $S$ to each state in your original DFA. This is also what the Rabin-Scott powerset construction algorithm does. So by doing a state encoding on the DFA we are trying to reverse engineer the set that the powerset construction algorithm started from.
In the traditional state encoding problem all encodings are legal, and there is some objective function (related to the amount of logic in the state transition function) that you are trying to minimize. To generate an NFA you need to solve a constrained version of the enconding problem where:
an encoding of $M$ bit identifiers to the DFA states represents an NFA iff for each symbol in the alphabet the transition function for each bit is a simple disjunction of bits. (No conjunction or negation is allowed.)
So you could enumerate all the $M$ bit encodings for all $\lg_2N < M\leq N$, and check whether each one satisfies the constraint. (Note that for $M=N$ the trivial "one-hot" encoding always satisfies the constraints, and gives you the DFA.) The enumeration is ridiculously large though, (Di Micheli's textbook gives it as something like $\frac{2^M !}{(2^M - N)!M!}$.) The reason I'm suggesting the CAD literature is that there are techniques for doing this search implicitly rather than enumerating (for example, by using BDDs, see Lin, Touati and Newton, "Don't care minimization of multi-level sequential logic networks," Int'l Conf Comp-Aided Dsgn ICCAD-90:414-417, 1990.
Example
Take the following DFA, (with a state encoding that I derived by cheating (I generated the DFA from an NFA using Rabin-Scott, and the encoding represents the subsets chosen by Rabin-Scott.))
If we call the bits in the state assignment ABCD, then when the input symbol is 1, the transition function is A=A, B=A, C=B, D=C. When the input symbol is 0, the transition function is A=A, C=B, D=C. This is a purely disjunctive transition function with no conjunction or negation, so this state encoding gives us an NFA. The states in the NFA correspond one-to-one with the bits in the encoding, and the transition function is as given:
Formulation as boolean satisfiability problem
The informal description above leads directly to an encoding as a boolean satisfiability problem. There is a set of variables that describes the transitions in the NFA, and a set of variables for the DFA state encoding that would be derived from Rabin-Scott for the chosen NFA. The transitions of the specific DFA you are trying to decompose are used to place constraints on the NFA transitions.
Suppose we are given a DFA with $N$ states for a language with $S$ symbols, and we would like to derive an $M$ state NFA, with $\lg_2N<M\leq N$. We will use the variables $y_{sft}$ to represent the possible transitions in the NFA. $y_{sft}$ will be true iff there is a transition in the NFA from NFA state $f$ to NFA state $t$ on symbol $s$. In the above example NFA, the alphabet is of size 2 and there are 4 NFA states, so there are $SM^2=32$ $y$ variables and $y_{0AA}, y_{1AA}$, and $y_{1AB}$ are all true while $y_{1DA}$ is false.
We will use the variables $x_{dn}$ to indicate whether or not the Rabin-Scott algorithm should include NFA state $n$ in the set of states labeling DFA state $d$. In the example above we have $N=8$ DFA states and $M=4$ NFA states so there are 32 $x$ variables. In the example above suppose the bottom-most state (the one labeled "1011") is state $k$, then $x_{kA}$, $x_{kC}$, and $x_{kD}$ are true while $x_{kB}$ is false.
Now the constraints. First of all, Rabin-Scott must find a different encoding for each DFA state, so for the DFA states $i < j$ and all NFA states $\{A,B,\cdots, D\}$:
$$
(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).
$$
Next it must be the case that if Rabin-Scott found a transition from DFA state $i$ to DFA state $j$ on symbol $s$ then for each NFA state $k$ included in the encoding of $j$ there must be an NFA state $l$ from the encoding of DFA state $j$ such that the original NFA had a transition from $l$ to $k$. In the example above, on symbol "1" there is a DFA transition from DFA state "1000" to DFA state "1100" so there must be an NFA transition from NFA state A to NFA states A and B and no NFA transition from NFA state A to either NFA state C or D. So for each of the $o(SN^2)$ edges in the DFA we have the constraints:
$$
\begin{eqnarray*}
x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\
x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\
& & \cdots \\
x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}.
\end{eqnarray*}
$$
Finally we need to deal with the start and accept states. The DFA start state is encoded with the union of the NFA start states, so the DFA start state better not be encoded with the empty set, so $x_0A + x_0B + \cdots + x_0D$. And finally we need a set of variables $f_n$ to indicate whether each NFA state is an NFA accept state. It must be the case that the encoding for every DFA accept state contains at least one NFA accept state and that the encoding for every DFA non-accept state contains no NFA accept states so: $x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$ for DFA accept states $i$ and $\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$ for DFA non-accept states $j$.
