I have the exact same problem described in this thread:
http://www.gamesas.com/topic/1216841-npcs-teleport-everywhere/?hl=navmesh+teleport#entry18244972

Where, instead of just walking from one patrol link to another, my NPCs instead walk in place for a few seconds, then teleport a few feet towards their destination. From testing, I know it's not a problem with the statics they're walking on or the navmesh (since I've made/remade them with several times).

I tried making an .esm by renaming the .esp to .esm, then loading it in skyrim, and saving without making any changes, but that didn't work.

Is there any solution for this?

I had that problem in New Vegas not Skyrim, and making it an esm did fix it. But that was due to the infamous 'navmesh bug' which Beth actually fixed in Skyrim in like... Maybe 1.3 or 1.4? (Somewhere back there several patches ago) So that shouldn't be causing you problems anymore.

For me the only thing that makes NPC's get stuck then teleport is if they actually get stuck, like if they run into... say, a table they'll bump into it for like 15 seconds then suddenly teleport closer to their goal.

So, I would assume that your navmesh is simply not done correctly? Can you post some pictures of it in the CK so we can see what it looks like?

Apparently I don't have permission to post links, so I think you'll have to copy and paste my links into a new tab, sorry for the annoyance

I set up a new navmesh real quick with a basic patrol. Only spent about 30 seconds on it but made sure to finalize.

/NVrrjLz.jpg

Path test with the NPC:

/Mn5naoi.jpg

Also recorded what it looks like so you can see what it looks like in game:

/watch?v=b1RYSrMBaTI&feature=youtu.be

Thanks for the response

Also, if it helps, this is an exterior worldspace that I've been working on for a while now. I don't have any other navmeshes set up in this version of the map since I deleted them all once I started having issues

My worldspace LOD wasn't installed when I did the tests so on the off chance that was causing the problem, I deleted all the current LOD textures/meshes/lodsettings and regenerated. LODs work perfectly, but the npc is still warping around

I'm out of ideas on what could be causing it