So is this problem unavoidable, as in there is no way to solve this without adding more mechanical parts to the system?
You could hack the library to remember the state of the motor when it was de-energized. But you would lose that if you powered down the Arduino.
how could an encoder solve the problem?
Some encoders have a "home" pulse built in. There are also "absolute" encoders that give you an actual angular position, (but these are very expensive).