After thinking about it even more, we could even move the search box down to the fixed header. It's pretty sparse anyway.

Something like:

form[action*="search"] {
position: fixed !important; z-index: 1;
bottom: 20px !important; right: auto !important;
margin-left: 560px !important;
}

Just gotta find a spot that it looks good in. Although, I still think the search looks really good absolutely positioned below the <dl>, but its your style, up to you.