I've been experiencing this, as well. I tried sending gifts to people, in attempt to get different items in return. I'm not really sure why, but I sent a letter to Bob yesterday, without a present, and he sent me a gift back with a nice letter. I sent him a letter back today with a gift attached, though.
Los Angeles Kings (49-28-5)
I'm not entirely sure if this is the same in New Leaf, but it seems to be working for me. In the previous AC games, sending a letter that was written as so: "Hi! How are you? Good bye!" with a present attached, always guaranteed a return gift. So far, I have always received a present from my neighbors.