>We could also just allow them to "bury" themselves into earth, then "unbury" themselves at a randomly chosen close location.

That is pretty much what they do - with the only restriction that the exit point may only be such a tunnel entrance. That tunnel entrance is pretty much your granite wall from your example: You usually leave it alone, but if it, for example, is directly where you want to mine something you might have to fight the animals or work your way around it.
That's pretty different to animals just randomly coming out of the ground and killing your Clonk - I think the latter might just be pretty annoying. Especially for new players.

>An enemy that you can defeat by getting it stuck easily is strictly more interesting than an enemy that you can't get stuck at all

An animal that you can get stuck by baiting it into a trap or constructing a traphole out of loam, sure - that may be pretty interesting.
I am talking from my experience in CR with different sorts of AIs.

>Animals should have the same role as, say, a granite wall at the same place: Normally just left alone, but for certain tasks a problem that needs to be solved.

Well, you are saying exactly what I mean: The granite wall isn't the main thing the player has to care about either. It's just another part of what he needs to take care of. Like the animals.