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.