The vinegar thing works if the rocks are really calcerous; I once did it on Cichlid Sand and it fizzed like soda pop. But for those rocks that are low in calcium content, you need a stronger acid.
Someone mentioned that one of the bottles in the AP nitrate test kit would do the trick, though I forget which one of the two. (Someone know?) And it worked for me.
One more thing - make sure that where you get your rocks is not a place where the potential for chemical fertilizer or pesticide runoff occurs. That stuff is nasty and I'm not sure i would trust it after even a bleach boiling.