From my personal experience it took my LO 4 weeks to be completely symptom free, that is no mucuos or blood in his stools, no reflux symptoms, no ezcema. I am still BFing and avoiding dairy/soy/egg/tomatoes/nuts after going on an total elimination diet. I think it took so long for us because at first I only eliminated dairy and then about a week later soy, and then about a week later I went on the TED diet to figure out he has problems with egg and tomatoes. Hopefully you won't have to go so extreme, but my point is it can definitely take time for your LO's gut to heal, it has to "recover" so to speak.
Also, for what it's worth Nutramigen is a milk-based formula but is gentle for babies with a dairy allergy because it is broken down into small protein chains making it easier for babies to digest. HOWEVER, some babies still can't handle the broken down proteins in Nutramigen (or Alimentum) and need an amino-acid based forumla like Neocate or EleCare. These formulas are made with free amino-acids (the building blocks of protein) basically doing all the work for your LO so that they don't have anything to react to, YKWIM? You would have to start with Nutramigen and see how your LO does, and if still not better try Neocate or EleCare. Or of course, giving BFing some more time and make sure you have ALL dairy and soy out of your diet.