Rather that using <span>'s for your underline effects, why not simply use the :first-letter psuedo-class and apply the underline that way (since all of your accesskeys are the same as the first letters).
Also, if you were to have this sort of setup:
<h1><span>Flexible Web Development. When having a flexible web site is crucial.</span></h1>
You could then apply the following styles to it:
background:url(bg) no-repeat top left;
That way, you would still have your main logo, but when styles are disabled you would have some main page header text to display (that search engines would also pick up on).
I've not checked your styles, but it seems to me that you could remove your #nav <div> tag and give the ID to the <ul> tag instead, then you'd dump a tag that you don't need, like I say though, I've not looked at the styles.
I notice that you don't have a skip navigation link in there, if you were to add one in users with screen readers could use it to jump past the list of links at the start of every page, rather than having to sit and wait.
Perhaps you could also centre your layout using margin:0 auto; on the #container and text-align:center; on the body tag, currently the layout hangs off the left hand side of the page (where it cannot be scrolled to) on 640x480.
Try and remove all decorative images from the page and add them in as backgrounds. It will make it easier in future to change the images on all pages, and also remove some of the tags from your markup.