So my field of study is concerned with Arabic and the Arab lands, and basically receipts are some of the earliest and most extensive documents we have in that language. The Geniza documents http://en.wikipedia.org/wiki/Cairo_Geniza#Contents_and_significance are mostly records of what today we would call receipts, so basically as soon as that society became literate they started making receipts.

My understanding is that the same is true of much, much older societies. I haven't studied it in depth so I can't point to a collection of documents like I can with the geniza, but my understanding is that in ancient Egypt receipts and accountancy records were written on papyrus and have mostly been lost (in comparison with the religious texts of hieroglyphics) while in Mesopotamia cuneiform bills of sale recorded on clay tablets are some of the oldest writings we have.

For example this "receipt of a dead sheep" from 2041BC http://www.metmuseum.org/collection/the-collection-online/search/325267

Again, not my field so I'm sure someone here can easily point out older examples, this was just some quick googling on my part.