Remapping/disabling the arrow keys as has been suggested is a great way to force yourself not to use them.
Another thing to consider: if hitting Esc on your keyboard is at all uncomfortable you might wish to remap Caps Lock to Esc in your OS. For me this was a hugely helpful step, as Esc is an awkward reach on my KB and that was another obstacle that kept me in Insert mode (as it was hard to get out). Having Esc on Caps Lock makes it a tiny reach and jumping in and out of Insert mode is very fast.
For learning advanced stuff in Vim the best resource is the :help, but for getting the basics down you just need to do it; it's muscle memory more than anything. You say you know search. Consciously use it as a navigation tool. The searches [/, ?] and the inline char based searches [f, F, t, T] are some of the key Vim nav tools. Just use them; comboed with the disabled cursor keys you'll be navigating on muscle memory alone in no time.
Text Objects. Easily one of the best features of the editor. This is the other thing to immediately consciously practice. Things like 'yiw', 'dit', etc. are so powerful and fast; learning and making use of them alone will make you feel like a Vim user.
Once you've got text objects and basic navigation down, then it's time to move on to reading and learning from the :help regularly and scouring the web for awesome plugins. Seriously, you can use Vim for years and have an "ah ha!" moment accidentally stumbling on some obscure tidbit in the :help you'd never known.