I'm in the temple of fist, and there is the pile of skulls that just drains my strength, and tells me "search failed". I've tried different things, but none help. So is it possible to actually serach this (higher Perception) or is this just a red herring?

Also, what are bones need for? Making wands?

You need to have Perception skill on active character in order to be able to search piles of skull. You need one character with Perception skill at 4 in order to complete one of main quests anyway. Perception at 4 Expert is sufficient to search through any pile of skulls without harm and with 100% success.

Bones can be traded to one of Free Haven citizens (he lives in one of the houses near Temple of the Moon). 1000 gold per bone and big reputation drop.

Oh great. Another skill I have to invest in...

Thanks.

Also make sure you only click on them once, subsequent clicks give you the status ailment regardless of perception I think.