Every vanilla map has every resource so you should find gold on the map. Custom (modded) maps should in nearly all cases have all resources as long as there are enough deposits.

Most likely you haven't reached all deposits. Some may need a bridge for the Bailiff to reach the deposit. The Coastal map in particular has deposits on an Island as well as to the right of the map (looking in from the sea) that are at the bottom of a cliff. A bridge can be used to reach these.

There is a minerals overlay that should help identify any you might have missed. Click the overlay and you will see the green circles around deposits.