https://github.com/kabir/jboss-msc/commit/409636359741dcc2e1b9345096d33e6625d64136 contains a test (testServiceRemove(), the other one actually seems to pass) which does the following:

Install Service A which depends on Service B which depends on Service C.
Remove Service B and C.
Install Service B and C again.

A does not get moved out of the PROBLEM state since the transitiveUnavailableDepCount is 1. This does not happen every time when running this isolated test but happens almost every time for me in AS when doing the steps to perform https://issues.jboss.org/browse/AS7-3085.