[andrewas]

Bleeding damage works as well - anything that puts a 'damage for x rounds' on the target will bypass the immunity and finish him off.

INT drain should also work, but thats slightly less useful.

But, properly, you use Fire or Acid damage. Certain species of trolls require different elements, but they dont show up till ToB.