On the affected machines in the Mail client hunt around in the menu item "Window" and launch 'Connection Doctor". Use that pane (click the 'Show Details' button) to see if Mail is connecting to the server(s) correctly.
Plus are these Macs are on email Server? Or are all these problems just on email the YOU send?