In the UK almost, where SD 16:9 is commonplace (and used for most broadcasts on digital TV), our set top boxes commonly output 16:9 SD (full height anamorphic, not letterboxed) via Composite, S-video and RGB (*) (and in some cases component and HDMI)
UK DVD Recorders will usually accept Composite, S-video and RGB (few have component inputs) - but many do not detect the three formats of aspect ratio signalling in use (WSS - in PAL this is on Line 23 and is a digital line of data a bit like Closed Captioning, Pin 8 on our SCART socket can have two different voltages to signal 4:3 and 16:9, and S-video can have a DC voltage offset added to the C signal ISTR)
This means that your set top box outputs a 16:9 SD signal (anamorphic) but your DVD recorder records this as if it was 4:3. On replay you therefore get a tall and thin picture in the middle 4:3 section of the screen.
The best solution I have found for this was to use a DVDRW disc for the original recording, rip it to my PC losslessly, run it through DVD Patcher that lets you alter the MPEG2 headers in the video stream (to switch the aspect ratio flag from 4:3 to 16:9) and then burn this back to a DVDR, allowing me to use the RW disc. I also used this as an opportunity to remove ad breaks if required.
I'm not familiar with US set top boxes being discussed here, and whether they will output a 16:9 SD full-height anamorphic image (rather than a letterboxed image in a 4:3 raster), but every UK HD set top box I have seen has this option for its SD outputs, mainly because many people still have SD 16:9 displays in bedrooms etc., and want to to route the SD outputs from their HD set top boxes to these.
(*) In the UK (in fact most of Europe) we have had an SD RGB interconnect standard since the 80s via our 21-pin SCART connector, and it is pretty universal for DVD players, digital TV set top boxes, games consoles etc. to output RGB SD video on this connector (offering SD component quality, and an improvement over SD composite or SD S-video). Many, but not all, DVD recorders also record from an RGB SD SCART input - allowing excellent digital TV recording. AIUI SCART is all but unheard of in the North American market (a bit like the Japanese have D connectors for component analogue video on a single connector, rather than multiple RCA phonos)