Well, in mencoder, to crop you can add this option
-vf-add crop=x,y
where x and y are the new resolutions (centered in the screen). So if you had black bands of 80 pixels on top and bottom, on a 720x576 pixel screen (kinda standard for 16:9 cinema screens encoded in widescreen), then you would add:
-vf-add crop=720x416
EDIT: this should read
-vf-add crop=720:416. END EDIT.
See the Wikepedia entry for the
Miniplayer for a good typical command-line that will also maintain the image proportions, and take care of the multiples-of-16 requirement for video resolutions.