Unfortunately, I still haven't figured out a way to fix it and have done all the steps you listed. I've started to kick around the idea of replacing the unit all together. If the Android Auto units were cheaper, it'd be already done. I tried relocating the GPS antenna, but that didn't seem to have any effect. The only sound sources that don't lag are SiriusXM and HD Radio.
I wonder what the cost would be if I sent it back to Kenwood, or if they'd service it at all since I messed with the maps.
I hadn't looked at the pure android head units before, but will definitely need to keep an eye on this. I wonder when their 5.0 versions will come out.
All the things you describe mine does the same exact thing! However I do not have the updated maps. I need see my firmware was on 13 so I was hoping this was the issue. Everything else on the unit acts how it should for me... It is just the Nav. I am going to contact the the shop. I actually have a Clarion NX602 that was pulled from another car of mine. I am thinking of putting this one in and sending the Kenwood off to be repaired. I prefer the kenwood but man!!! Shame on them! I have never had an issue and have always bought their high dollar units and this clearly is an issue across the board on these. I really like the sound stage and eq on it so I want the unit but operating as it should as I use Nav alot and it has been rendered useless.