I noticed that when I change this line:
Velocity = Velocity + acceleration * deltaTime;
Velocity = Velocity + acceleration;
It appears to work like I expect, it also fixes the seek steering behavior. Can anyone explain this? I thought deltaTime had to be included when calculating both velocity and position. Maybe there is still a problem hidden somewhere.
EDIT: I should add, at higher speeds I need to increase the max force as well.