To get some feeling for the problem, we make the following simplifying
assumptions:

1. $B$ is independent of $x$, say $B \in S(\overline{\mathbb R}_+)$. 

2. $A$ admits a (holomorphic) functional calculus.

3. There is a (holomorphic) function $h\colon \sigma(A)\to\overline{\mathbb H}_-$ such that $\bigl(i\tau - \lambda\,\hat{B}(\tau)\bigr)\bigr|_{\,\tau=h(\lambda)} =0$ for $\lambda\in\sigma(A)$, where $\hat{B}(\tau)=\int_0^\infty e^{-it\tau}B(t)\,dt$ is the Fourier transform of $B$.

Then it is readily seen that 
$$
  u(t) = e^{ith(A)} u_0
$$
is a solution of the original problem. Notice that, in general, *one can only solve backwards in time*.

There are several difficult points with this approach, the two obvious ones being:

* The range of $i\tau\,/\,\hat{B}(\tau)$ might miss parts of the spectrum of $A$. This puts restrictions on the initial value $u_0$.

* There might be several choices for the function $h$. This leads
  to non-uniqueness of the solution $u$.

Here is an example, where this approach works: Take $B(t) = H(t)\,e^{-t}$. Then $\hat{B}(\tau)= \frac{1}{1+i\tau}$. Choose $A\in \operatorname{Op}S^2({\mathbb R}^n)$ with principal symbol $|\xi|^2$ and $\sigma(A)\subset\{\lambda\in{\mathbb C}\mid \Re \lambda>0\}$. Then $h(\lambda) = \frac{i}2\left(1-\sqrt{1+4\lambda}\right)$. It follows that $h(A)\in \operatorname{Op}S^1({\mathbb R}^n)$ with principal symbol $-i\,|\xi|$. This implies that the operators $e^{ith(A)}$ for $t<0$ belong to $\operatorname{Op}S^{-\infty}({\mathbb R}^n)$, i.e., they are regularizing, and there is no propagation of singularities.

---

ADDED: I'm not aware of any holomorphic functional calculus for pseudodifferential operators - with $m>0$ and not necessarily having $A$ be normal (i.e., $AA^*=A^*A$ as unbounded operators in $L^2$) - which does what is required here. 

Indeed, $\hat B$ extends to a $C^\infty$ function in $\overline{\mathbb H}_-$ which is holomorphic in $\mathbb H_-$, with
$$
   \hat B(\tau) \sim \sum_{k\geq 0} \frac{B^{(k)}(+0)}{(i\tau)^{k+1}} \quad
   \text{as $\tau\to \infty$ in $\overline{\mathbb H}_-$}
$$
(and this asymptotic expansion can be differentiated any number of times).  Therefore, assuming $B(+0)\neq0$, one has
$$
  \frac{i\tau}{\hat{B}(\tau)} = -\,\frac{\tau^2}{B(+0)} + O(\tau) \quad \text{as
    $\tau\to\infty$ in $\overline{\mathbb H}_-$.}
$$
So, one would expect $h(A)$ to belong to $\operatorname{Op}S^{m/2}$ and to have principal symbol
$$
  -i\sqrt{B(+0)} \ a_m^{1/2}(x,\xi),
$$
where $a_m(x,\xi)$ denotes the principal symbol of $A$.

Of course, *$h(\lambda)$ need not be an algebraic function of $\lambda$* - as was the case in the example above - and then in order to prove such a result one cannot directly appeal to known facts about complex powers of (hypoelliptic) pseudodifferential operators.

Still, as 
$$
  h(\lambda) \sim \sum_{l\geq0} c_l\lambda^{1/2-l} \quad\text{as $\lambda\to\infty$}
$$
in a suitable sector depending on the choice of $B$ (again, this asymptotic expansion can be differentiated any number of times), with $c_0 = -i\sqrt{B(+0)}$ as just seen and $c_l$ for $l\geq0$ computable in terms of $B(+0),\dots, B^{(l)}(+0)$, there is a good chance that such a result holds. See also this previous <a href="http://mathoverflow.net/questions/87937/functions-of-pseudodifferential-operators">post</a>.