Matching a set of paths to an incrementally generated graph
I'll outline a solution to your problem.  There are two key insights: (1) each path can be analyzed independently of all the others; (2) the best match can be computed using dynamic programming.  I'll start with a simpler version of your problem and build up to a solution for the full problem.

Finding the best match for a single path

Suppose we have a single path (from graph A) and we want to find its best match in graph B.  This can be solved with dynamic programming.

Let $P$ denote the path from graph A, and $P_k$ denote the prefix of the graph containing its first $k$ edges.  If $v$ is a vertex in $B$ and $k$ is a natural number, define $f(k,v)$ to be the number of edges present in the optimal match of $P_k$ inside graph B, such that the match ends at vertex $v$.  Then $f(k,v)$ follow the following recursive relation:

$$f(k+1,w) = \max(\max \{f(j,v) : v \to^* w,j \le k \}, 1 + \max \{ f(j,v) : v \to^* v' \to w, j \le k\})$$

where the former max is taken over all $v$ such that $w$ is reachable from $v$ in B, and latter max is taken over all $v,v'$ such that $v'$ is reachable from $v$ in B and there is an edge from $v'$ to $w$ in B whose label is the same as the label on the $k$th edge of $P$.  Also, we have the base case $f(0,v) = 0$ for all $v$.  Finally, notice that the number of edges matched in the optimal match for $P$ is given by $\max\{f(k,v) : v \in V\}$.

This recursive relation immediately gives us a dynamic programming algorithm to compute the number of edges matched in the optimal match for $P$.  You can also augment the algorithm to retrieve the match itself, if desired.

The running time is polynomial.  Suppose the path has length $\ell$ and graph B has $n$ vertices and $m$ edges.  Then there are $O(\ell n)$ subproblems, and each subproblem takes $O(m \el)$ time to solve (on average), so the running time is $O(nm \ell^2)$.  [It might be possible to further improve the running time by decomposing B into strongly connected components and only computing $f(k,v)$ values for one vertex $v$ in each strongly connected component, but I haven't tried to optimize this algorithm.]

Note that this gives the exact optimum, not an approximation.  It's not a heuristic -- it always gives the optimal solution.

If you don't find the dynamic programming algorithm intuitive, here is another perspective.  You can think of this from an automata theory perspective.  Suppose the path has edge labels $e_1,\dots,e_{\ell}$.  Let $M$ be the automaton that accepts every subsequence of regexp $\Sigma^* e_1 \Sigma^* e_2 \Sigma^* \cdots \Sigma^* e_{\ell} \Sigma^*$ (this is a regular language, so it has a NFA, call it $M$).  Form the parallel composition of $M$ and B, using the product construction; call it $M'$.  Now look for the longest path in $M'$.  This is exactly the optimal match you are looking for.

Finding the best match for a collection of paths

Now suppose we have multiple paths and want to match them all to B.  Well, it turns out that the optimal way to match a collection of paths is to consider each path separately, finding the optimal match for that path in isolation (independent of all the other pairs), and then combine these matches.

So if we have $q$ paths, we can just invoke the algorithm above $q$ times, once for each path.  The running time will be $O(nm \ell^2 q)$.

Dealing with changes to B

In your problem, each time you find the best matches for a collection of paths, you then update B to get a new graph.  This can be easily handled by simply running the algorithm from scratch again on the new graph.  In each round, you run the $O(nm \ell^2 q)$-time algorithm from above on the current graph B.  Then, you use whatever technique you have in mind for growing the graph B, and start over again.  This doesn't let you re-use work from previous rounds, but it's a very simple technique, and it computes the optimal solution.