Hey Will,
This sounds like a fairly large undertaking, though I doubt we'll be able to give you all the answers - maybe a few comments to get you headed in the right direction will help.
1) I'd start looking into the options provided by SQL Server's Full Text Searching and the options discussed in this article: Fuzzy Lookups...
2) this will be accomplished by storing information about your paying customers in the database - so you can identify them. you can then write SQL queries that look specifically for the paying customers and return them. You could accomplish this in a number of ways through SQL - my recommendation is to focus on storing the information so that paying customers can be identified first.
3) My company, Engage Software, has a module called Engage: Locator that is purposed around listing business locations. You may check this out to see if you can make it work -- also you could always purchase the source version and modify it to suit your needs if it comes close!! There is also mapping functionality integrated into the module.
4) think site maps, keywords, friendly urls, and proper page redirection, also think about the importance of well formed HTML, the XHTML/CSS and light-weight pages. There are many DNN features, skins, and modules to assist you with these. Ifinity Friendly URL provider is a very powerful HTTP module - Pageblaster is another module that can give you a lot of power over your site's output (URLs, html files, etc...) using the built in SiteMap in DNN and submitting to search engines is a must!
Good luck and take care!
Ian