Checked now myself, doesn't seem to work 100%, or I might be missing something.
If I hit that link on my profile, I get 27 hits, earliest being January 2013.
Then I click another link saying "find older messages", which brings me another 20 (January 2013 - September 2012).
Older threads don't seem to show up (like e.g. the ones in my signature).
Not a big deal, but I wonder why o_O (I'd guess indexing is not yet completely done, right?)