The most innovative ways, might also actually be the least innovative ways:

* Send them hand written thank you notes for their business.

* Interview them about their successes, and highlight them in your blog/on your site.

* Where appropriate, send them business from other customers

* With their permission, talk about them in your PR and interviews even more than you talk about your product

* Tell them whenever someone signed up because of their personal referral

* Actually answer the phone