Ciao,
per risolvere il problema dovresti impostare il padding del div che contiene il menu, e non il margin dei link. Il margin infatti riguarda solo l'inzio dell'elemento, ma poi se vai a capo non viene considerato, invece il padding del div è la spaziatura tra il bordo e ogni altra cosa contenuta al suo interno.
Comunque ti consiglio di fare il menu con una lista, ormai fanno tutti così a partire dallo stesso W3C.
Dai un'occhiata [url=http://www.constile.org/template/menu_verticali/]qui