Separate Address Table, Latitude, Longitude
The right answer is choice #5: use PostGIS. An example from OpenGeo:


  "Note the magic &lt;-&gt; operator in the ORDER BY clause. This is where the magic occurs. The &lt;-&gt; is a “distance” operator, but it only makes use of the index when it appears in the ORDER BY clause. Between putting the operator in the ORDER BY and using a LIMIT to truncate the result set, we can very very quickly (less than 10ms on a 2M record table, in this case) get the 10 nearest points to our test point."


(emphasis added)