Ok, I'm gonna try to explain this... english it's not my mother tongue, and the "problem" I'm experiencing its quite rare to describe, so be patient with the text:

My character walks in a really weird way. It seems to be some kind of colission/whatever problem, because every x steps (lets say, every 20 steps), the character hangs in a spot and suddenly appears a bit far from it.

I mean, when yoy walk, you take one step, then another and so on, and the distance you are covering its constant. Not in Arx, where I can give 3 steps, the fourth won't move and suddenly the character appears in the spot he would be if he would have walked 10 steps.
Maybe the worst case of this "bug" was in the first goblin outpost: I was crossing a room's door, in the middle of the room two enemies and BAM! suddenly I had crossed the whole room and was behind those enemies.

So, unless there's some kind of "random teleportation spell", there's something weird going on... any ideas?

(Im running the game in a Windows XP SP2 system, and I have enough computer to move it smooth with all the stuff to the max)

While the game is running hit ctrl+shift+escape.

This will bring up the processes tab of your Task Manager, click Show processes from all users.

Right click on Arx.exe and select "Set Affinity..."

Limit it to only Core 0 (uncheck all other Cores). You must do this every single time. This... should fix your problem.

Thought I had already answered this :s

Dind't work at all. In fact, after that trick I started to experiencie several graphic issues. Plus, it doesn't seems to have anything to do with the speed of the processor: If my character "jumps" from position A to position B, the rest of the characters keeps behaving normal.

Do you have an AMD CPU? If so install the AMD Dual-Core Optimizer and see if that helps.

Nope, I got a Intel Dual core :(

Also, I got XP up to date (There was some kind of Windows Fix for dual core systems).

Graphical issues have absolutely nothing to do with the processor. it's strange you experienced them after you limited the cores.

What graphics card are you using?

This must be a graphics card incompatibility.

Hmm. Try the unofficial patches--Arx Fatalis Fixed and Arx Libertatis. These fix and modernise the code in various ways so may well resolve your problem.

I'm having the exact same problem. It doesn't seem to be as severe as OP's issue is, but it's there. I am currently running it with Arx Liberatis and all of the other community patches, and it seems to run flawlessly, with this one tiny issue. It's almost as if the collision box around the character is clipping with some of the collision meshes on the ground while the walking animation continues. The end result is that the character leaps forwards a few feet after finally realizing that some distance should've been traveled. Not a game breaking issue, just an oddity. (also, I have no idea if that's really the issue or not, it's just my postulation.)

And no, it's not my rig. I'm running a fairly high-end PC and having absolutely no performance issues whatsoever. The jittery movement does not seem to affect frame-rate at all. Windows 7, nVidia GeForce 460m, 2 Intel Core i7 Processors.

First noticed it outside of the goblin prison, just before reaching the first tavern.