I had the same problem with my Dash. Here's the story and the fix. Even still, the quality is not up to par with my Toshiba Gigabeat S60 PMC, but it's still good enough...
In WM2003 WMP10 you could force WMP10 on your phone to ask WMP10 on your PC to encode video to full screen size by editing the registry values under this key: [HKLM\SOFTWARE\Microsoft\MediaPlayer\ASFCodecs\Video] setting the PrefferedHeight to 240 and the PrefferedWidth to 320 for each video codec.
Unfortunately those reg keys are no longer in WM2005, the reg key [HKLM\SOFTWARE\Microsoft\WMDM] has a value WMDMCapabilities which points to the file: \Windows\WMSyncCaps.xml
Copy this file to your PC, and open in Notepad. Edit all of the "Height" and "Width"
values you can set them to 240 and 320 respectively (set all of them).
Save the new file as WMSyncCaps2.xml and place it in the \Windows folder on your phone. Use a third party file explorer (such as Resco) to delete the original file from your phone, then rename WMSyncCaps2.xml to WMSyncCaps.xml. I forget the exact sequence -- you may need to rename the original file to something else before you can delete it.
On your WMP11 on your PC, choose the Tools – Options menu, choose the Devices tab, choose the Advanced button, and click Delete Files.
On your Phone, find the WMPInfo.xml file on your Storage Card. Back it up somewhere, and then delete the file.
Reboot the phone
and the PC, and try to sync, When you play back a video in full screen
(hit 0 on phone to switch to full screen) it should fill it rather than
being boxed in black.