There are lots of options for geocoding addresses out there including MapQuest, Google Geocoding API, Yahoo PlaceFinder and some open source options such as Nominatim and Gisgraphy. Gisgraphy has a cool tool that lets you compare the accuracy of the various geocoders.
If you are geocoding for Canada, one pay service that seems to be extremely accurate is geocoder.ca. This wasn't an option for me because even at the reasonable price of $1.00 for 400 geocodes, the costs can add up.
Gisgraphy is a cool option however, the accuracy is a bit of an issue in tests and I don't want the hassle of running a GIS server. Geocodes are usually only accurate to the street level, and sometimes they are farther off than that.
Google has a restriction that you must use their maps if you use their geocoding service so this doesn't give me the flexibility I need. They also only allow 25000 static map requests per day which I could exceed.