Were they a member last year?
Memberships have three primary dates, the join date (member since), start date and end date. The join date is the date the contact first signed up for a membership with your organisation. Unless it is altered manually it will never change from that first value. The start date is the date the current continuous period of membership began. The end date is the last day of the current membership.

Examples for a 12 month membership:  


Mary joined on 1/1/2011 and has always paid her annual membership fees when they are due  She will have a member since date of 1/1/2011 and a start date of 1/1/2011 as she has been continuously financial since 1/1/2011.
Peter joined on 1/1/2011. At the end of 2011 he let his membership lapse.  He rejoined on 1/1/2014 and has paid his membership fess regularly since then  when they are due.  He will have a member since date of 1/1/2011 but a start date of 1/1/2014 as he has been continuously financial only since 1/1/2014.


So your member who joined in 2012 (presumably for 1 year)  but didn't renew until 2016 should have member since = 1/1/2012 and start date = 1/1/2016. 

The exact search filters you need to use depend on the duration of your memberships, whether they are fixed or rolling (rolling makes it much more difficult) and what hapens if they join on, say, 1 October rather than on 1 January.

Assuming a fixed 12 month membership that always start on 1 January you can find all contacts who joined previously, are currently financial(2016) but weren't financial last year (2015) by using Advanced Search with membership filters:
 - member since "To" date of 1/1/2014 (no need to set "From" date)
 - start date "From" date of 1/1/2016 (no need to set "To" date)

This won't work if you have modified the membership settings somehow (perhaps by setting member = yes for the expired membership status), or if this is a new CiviCMR install and the old membership data wasn't imported correctly.