Let $C(H) = B(H)/K(H)$ be the Calkin algebra.

> Apparently weak equivalence classes are strictly larger in general.

Yes, the easiest example will be $A = C(H)$ with $\epsilon_1: C(H) \to C(H)$ the identity map and $\epsilon_2: x \mapsto s^*xs$ where $s \in C(H)$ is the image of a unilateral shift $S \in B(H)$. These are weakly equivalent since $s$ is a unitary in $C(H)$, but they aren't strongly equivalent. We can see this because if they were then there would be a unitary $u \in C(H)$ that comes from a unitary $U \in B(H)$ such that $s^*xs = u^*xu$ for all $x \in C(H)$. That is, $su^*$ would commute with everything in $C(H)$. This would mean that $SU^*$ commutes modulo the compacts with everything in $B(H)$. But $SU^*$ is an isometry from $H$ onto a codimension one subspace of $H$, and it's easy to find an operator whose commutator with it isn't compact. (Use the Wold decomposition.)

> Is there an obvious K-theoretic reason for this? In particular, does the unitary group of the Calkin algebra has something to do with this?

Here is a good way to think about it. We have a C*-algebra $A$ sitting inside $K(H)$ and a unitary $s \in K(H)$, and we want a unitary $u \in K(H)$ that comes from a unitary in $B(H)$ such that $s^*xs = u^*xu$ for all $x \in A$. That is, we want $su^*$ to commute with $A$.

The unitary group of $K(H)$ has connected components indexed by $\mathbb{Z}$. The index $0$ component consists of the unitaries which come from unitaries in $B(H)$. For general $n$, the index $n$ component consists of the unitaries which come from partial isometries in $B(H)$ whose Fredholm index is $n$. A little thought now shows that finding $u$ with index $0$ such that $su^*$ commutes with $A$ is equivalent to finding a unitary in $K(H)$ with the same index as $s$ that commutes with $A$. So the question is whether $A$ has unitaries with arbitrary index in its commutant.

> Strong and weak equivalence are the same for abelian $A$.

I don't think this is true, though.  Let $A = l^\infty/c_0$, realized as the image of $l^\infty \subset B(l^2)$ in $C(l^2)$ under the projection from $B(l^2)$ onto $C(l^2)$. By an old result of Johnson and Parrott ("Operators commuting with a von Neumann algebra modulo the set of compact operators", *J. Funct. Anal.* **11** (1972), 39-61), $A$ is maximal abelian in $C(H)$, so any unitary in its commutant already belongs to $A$. But every element of $A$ has index $0$, since $A$ is the image of an abelian subalgebra of $B(H)$, and every abelian subalgebra contains only normal operators which all have index $0$. So $A$ is an abelian subalgebra of $K(H)$ which does not have unitaries with arbitrary index in its commutant.

I suspect that for every *separable* C*-algebra strong and weak equivalence are the same: you can find unitaries of arbitrary index which commute with any given separable subalgebra of $K(H)$. But I don't see a really easy way to show that.