New wp menu menu styling

Are you using CSS3?

You could use:

ul#navmenuid:first-child {
     border-left: 1px;
}

Or you could use (any LI that immediately follows an LI):

ul#navmenuid li {
     border-left: 1px;
     border-right: 1px;
}
ul#navmenuid li + li {
     border-left: 0;
}

Or you could use (any LI that follow an LI, even if not immediately):

ul#navmenuid li {
     border-left: 1px;
     border-right: 1px;
}
ul#navmenuid li ~ li {
     border-left: 0;
}

Lots of options via CSS, really…