You'll find the parts of Arinth's Legendary Staff in 3 separate dungeons spread across the game..
1.northern corner of the Northern Vai'lutra Forest
2.western side of Snowbrook Valley
3.SW corner of Isteru's Caverns
You have to be able to speak with the spirits...
If you need more details, just email me, and I'll send them to you..
Which mines are you dying in??