Re: How will something like Google Maps or Mapquest work in Pakistan?
short answer: yes. you need a GIS database and an efficient/intelligent search algorithm. Give me the database and I can make it for you. I looked into this because I was interested in making one (not in making the database)
most of the big cities in Pakistan have already got the GIS database thanks to a couple of companies, Worldcall and Multinet I know have got detailed enough databases to be able to map addresses (they're actually said to be detailed enough to map lamp posts on streets...) and they are in use by the many car tracking companies like Trakker. Since making these databases is not trivial by any means, the companies price it much beyond the means of an individual. So until a company invests some money into acquiring the databse, or worldcall itself decides it wants to use its database for that purpose, its not going to happen.
But the infrastructure is there.