As far as the problem of storing your 2.7m geographic destinations is concerned, the first thing that occurs to me is "RAM disc". Are you able to create a RAM disc, load your data into it, then just read it from there as you need it?
For the AJAX auto-complete feature, if you hunt around you'll find an AJAX search example that (from memory) searches for peoples' names. As you type in 'sam' (for example) in your search field, the database gets hit with e.g. 'SELECT NAME WHERE NAME LIKE 's%', then 'SELECT NAME WHERE NAME LIKE 'sa%', then 'SELECT NAME WHERE NAME LIKE 'sam%'. Every time the content of your search field changes, it triggers a new database search with whatever the content of the field is at that point in time.
One example is http://snippets.dzone.com/posts/show/1691, another is Radar – O’Reilly (look under the 'Using Observers' section, another is Ajax on Rails • The Register
I've built this type of 'active search' myself from these examples; it's VERY cool when you get it going, and you can get it going in a very short period of time. When I first demo'ed it, people shifted 180 degrees from "Why should we bother with this Rails stuff?" to "Let me at it".
Regards
Dave M.