pcolijn: there's a utility shipped with XFree86/Xorg that should take care of that, at least for xterm. Just do eval $(resize) in the affected window.
This used to happen to me a lot, and I think the reason it doesn't anymore is that I keep frames sized to take an 80x30 terminal, and specify that geometry in ~/.Xdefaults.
