That replacement evaporator certainly should have lasted more than 35k miles but you didn't say how many years that is or if you have a cabin air filter retrofit installed. That simple device makes a BIG difference in evap life. When I did my mine I couldn't believe how dirty it had gotten before installing a filter two years earlier. Your car also has 12 year old ac hoses and I can guarantee they're both leaking at the fitting crimped junctions. Look for any signs of wet oily deposites at those points. Although a hose leaking 2 cans of coolant every 3 weeks should be pretty easy to spot.