For searches, I believe you can just truncate the "search" table.
For private messages, it looks like it checks the last entry in pmtext for a given user. Since we
know that Jan 1 2016 is unix timestamp 1451606400, and the difference between 2012 and 2016 is 126230400, you can do this query:
Code:
UPDATE pmtext SET dateline = dateline - 126230400 WHERE dateline > 1451606400
You could also do similar queries on the post and thread tables (not all timestamps are named dateline so you might have figure out which colums are timestamps and run the query multiple times).
It might be a good idea to do a database backup before trying any of this.