POSSIBLE FIX
I started having this problem on 11th May, 2017. My "wrong starting point" was near an old location I had visited back in February. I tried everything from restarting the phone, disabling and enabling the app, updating, deleting updates, disabling Google Location History and then deleting my location history. Nothing seemed to work.
Five days later the problem persisted, so today I opened Account settings on my phone with an intent to sign off my current google account and try with another one to see if the problem was stuck to my device or my account, but before that I just randomly tapped on Sync Now. Upon completion I checked back in Maps and ta-da, it was showing the correct route!
Just my layman's guess, but it could have been that Maps was retaining old location data because it wasn't properly synced with the account and hence showed the wrong starting point in navigation, while it was getting correct live location through the GPS and hence the blue dot was placed correctly.