I was going to write something much the same. I work for a small consulting firm and we've dabbled with the idea of rewarding referrals. The main reason we haven't done it is fear of lowering the value of the referral. A referral from someone that gets absolutely nothing out of doing it means a lot. If you reward that person suddely your referrals are cheapened. You've actually lowered the value of your best marketing tool!

I also agree completely that you should reward the referral, not the result. We've had another consulting company refer us twice. One landed us a big client, the other came to nothing. Both times we gave the referrer a small gift (bottle of wine) to show our appreciation.