If you have to handle specific behavior for the new method in an existing type, of course you will need to add a new implementation of the method for that type.

As I understand the Expression problem, the limitation of programming languages is that they force you to modify the previous existing types even if the new behavior is a generic method that works the same for all types, so it should be enough to define it once for all classes. A virtual method in the base class should be able to do that.