Since your original rear derailleur did the same thing I suspect the problem is neither the rear derailleur nor it's adjustment. Whenever I encounter a rear shifting problem like that the first thing that I do is to check the hanger alignment. Most of the time that fixes it.