Back when iOS 7 was the new kid on the block, we discovered a trick that let you search texts for old photos [1] and videos sent between your contacts. Now that task is even easier in iOS 10.
Instead of scrolling through your message history, just go to a text conversation, hit the little "i" at the top right of the contact name, and you'll see all the attachments you've ever sent to and from that person. Ta-da! How easy is that?