Here's my sponge experience so far:
Try 1:
I went to a gardening/hardware store and picked up a largish sponge for about US$8 (I sniffed it, but it didn't occur to me to lick it

). I soaked 2 days in a bucket, 2 days in my leaf soaking bin, and 2 days in a fish tank. After all that soaking, I eagerly put it in my RCS tank. No negative reaction, but even after a week, the shrimp didn't seem to be interested in the sponge. They even seemed to walk on it less often than on the gravel...

Brand: Dutch Boy Dimensions Natural Sea Sponge
Try 2:
This time I headed for a crafts store. After a quick sniff, I bought a 4-pack of sponges (1 large, 3 small) for less than US$4. After reading Mustafa's posts, I just rinsed the large one and tossed it in. Same results as the first sponge.

So I took that one out and put in the 3 small ones. The two that look similar to the large one did not generate any interest (they're the ones in the back of the first picture below). Happily the last one, which looks hairier than the others, got some shrimp grazing on it.

After a week or so now, they seem less interested though
It's probably because it's a small sponge and they already ate the current goodies off of it.
If I get impatient, I might end up hunting for more sponges...