I agree entirely. English is a lot more regular than it's often given credit for. But I don't think used not to is going to fit into the system without some serious rule bending.Students often come away thinking that English is full of exceptions. And when I see an unusual construction, the first thing I do is ask whether it fits the system or not. If not, fair enough.
I would analyse it lexically i.e. think if it as a "chunk" that has entered the language rather than something that is being generated by rules. And it's become familiar enough not to raise eyebrows among many NSs, including me and Lorikeet.