Unfortunately, FrontPage 2003 isn't very good at keeping your code XHTML-validated. (Expressing Web Designer and SharePoint Designer 2007, in contrast, are very good at keeping your code XHTML-friendly.) So here are a few common things that you'll need to do in your pages for valid XHTML. (There may be others not listed here.)

1. First step - right-click in the Code View pane and choose Apply XML Formatting Rules. What this essentially does is to add closing slashes to empty tags -- for example,your <br> tags will be automatically transformed to <br />. This will probably fix 80% of the errors generated by the HTML validator that are along the lines of &qout;end tag for... omitted, but OMITTAG NO was specified" It will also take any uppercase HTML code and make it lowercase.
2. Now, go through and click on each of your images (that are actually embedded on the page -- you will see the <img ... /> tag in code view). Look at the HTML code. If you see anything that looks like border="0", you will have to delete it. For example -- <img border="0" src="/image.gif" alt="My Image Here" /> will need to be changed to <img src="/image.gif" alt="My Image Here" />. This should fix all of the "there is no attribute 'border'" errors.
3. Sometimes FrontPage will drop the closing paragraph tag (</p>). If you see errors that say: "end tag for 'p' omitted, but OMITTAG NO was specified," then look at the line and column number of the start tag (the validator conveniently lists it as the next item) to track down the opening of the paragraph. Then, in the HTML code, look for the end of the paragraph and manually type in the closing tag.
4. Did you add any FrontPage Link Bars to your template? If you did, they will not validate. You should remove the link bars and put in hard-coded links instead. (You might want to put those links into an Include Page for easier editing later.)
5. Did you add any Flash or Swish movies? If you pasted in the typical HTML code (it's a big block of code, with <object> and <param> tags all over the place), then it won't validate properly. Instead, use a solution like Deconcept.com's SWFObject embed solution:
   <a href="http://blog.deconcept.com/swfobject/">http://blog.deconcept.com/swfobject/</a>

By following the above steps, you should be able to get most of your site fully validated. There may be some other issues if you have used various scripts or components which will need to be dealt with on a case-by-case issue.