Hi Gerd,
I was a bit wrong with my analysis of Ottawa and Toronto. Toronto and Ottawa should be admin level 8 and the 'cities' within Toronto and Ottawa should be admin level 9 (as Orleans was already tagged). I've corrected the labelling issues in OSM but I didn't add the missing 'city' boundaries inside Ottawa.
I've attached a patch that corrects address search for Toronto and Ottawa. You'll need updated bounds data for this to work but I have confirmed that it's working. It would be nice to get this included in mkgamp.