In Ojaveda there was a crate placed up on a wall with a note on it that said something link "Ojaveda Mail Box: Leave your message in here or email it to [something]@gmail.com for delivery. The latter is preferred so nobody steals your message. Be sure to include the recipients name. Sender's signature is optional."
If you can't make any money from selling back books, I think it would reduce the amount of books stolen at least to some extent. Or, introduce a letter item that acts just like a book but isn't worth anything.
And yeah noobs might take a couple at first, but I would like to think that when they find out that the books have no use to them, and that they're being a douche by taking other people's stuff, they would stop.