This project is fairly simple yet, complicated.
So far the company was using a desktop application for tracking, routing, directions, etc.
Now they want a web version.
I was thinking about using microsoft's bing service or google's maps.
Which do you think would suit better?
For address validation you could use Google's Geocoding API. It's not a perfect solution as it allows for addresses that might be partially wrong. An example is a user typing in 3002 Such and Such Street when 3002 doesn't actually exist.
Also, if the link doesn't have to be internal then you can provide a link to Google maps with the format http://maps.google.com/maps?saddr=[STARTING ADDRESS]&daddr=[DESTINATION ADDRESS]
I'd imagine there is also a way to handle directions with the Maps API but I'm not sure.