To add address is simple, right? Modify the screen, modify the SP, blah, blah, blah. Lame. ??? Why is that 'lame'? In the end 'something' will need to be modified, correct?
When I build look-up screens with users, they often have a pretty good idea of what they want to search on. If anything, sometimes I give them too many search lookup options, for the very reason of what you're describing. But I really don't understand the 'lame' part.
How about take this to a logical extent? Give the user the ability to create a somewhat dynamic query using the fields in the table(s) that create the result set for the current screen. Well, that's a pretty broad description, but certainly do-able. I've had situations where a result set could be filtered by several sets of checkedlistboxes (i.e. Status1 has up to five statues, check the ones you want....status2 has 6 options, check the ones you want, Type1 has 8 types, check the ones you want, blah blah blah). I handle that with XML parameters in the stored proc. So depending on the requirements, it's doable.