What you want to do doesn't sound impossible to me. However, for my own part, I don't think I do need this kind of feature and so won't be able to help much. Guidance is possible, though. And no, nothing like this has been implemented yet.
Adding assumptions to expressions throws up a couple of questions: Where do you stick assumption-tags? A pointer to something in class ex might slow it down somewhat, though this needs to be tested. I think ex would be the way where to store it. The alternative would be a protected variable in class basic. You need to think about how to evaluate those tags. The trivial example you give suggests that each class' eval() function should check for members' property-tags, it could read them via the .info() method. (The info_flags class might need some careful restructuring, if this wants to be going into production use. It is pretty much hacked together.) If it gets in the way in the .eval() function, an alternative would be to add this checking to another evaluation-method. It can soon get very involved as soon as more than one variables are involved. There is some literature about this and one should carefully check what Maple does here.
The main algorithm I know works on polynomial: for univariate polynomials, it is known as Sturm sequence. For multivariate polynomials (systems) I believe it is still an active reseach field (search for example for publications of M.-F. Roy), technics involved are Sturm sequences generalizations and Groebner basis (BTW, implementing Groebner basis is one of my objective with my polynomial classes).