I could be missing something key in how to view a history of posts to my facebook wall and search tips for Facebook. But how would I go about searching my old Facebook link updates?
Rehashing from the comments.
Have you tried http://www.facebook.com/posted.php?id=[your facebook id] ?
Go to facebook.com -> your profile page and try any of the following
1) View Videos of Me
2) See All under Friends section
or go the Graph way
Another approach: you can download a copy of all your facebook data by going to your general account settings and at the bottom click "download a copy of your facebook data" (as of Jan 2014)... they will build a zip file archive of everything and email a link when they are done. The package contains a set of HTML pages... one of which is a page of everything you've ever posted to your own wall... then you can just open in a browser and do a "find" on the page.
currently it doesn't include all the comments on your post... but once you find your post you can see the date on it, and then go back in time on your activity feed to find the original post