Backing up to smaller drive

Have a look at Clonezilla, it may do what you are wanting. Most drive imaging programs also compress the drive as they go and the machine shouldn't come to you with the 500GB drive completely full so as long as you have at least a good proportion of that 250GB free I wouldn't worry too much.

Clonezilla's site states: "Filesystem supported: ext2, ext3, ext4, reiserfs, reiser4, xfs, jfs of GNU/Linux, FAT, NTFS of MS Windows ... (yadda yadda) For these file systems, only used blocks in partition are saved and restored. For unsupported file system, sector-to-sector copy is done by dd in Clonezilla."

The answers for How to transfer a RECOVERY partition to a new HD of a DELL Inspiron 1420? suggests that Clonezilla may be better (but slower) for saving the recovery partition.

I use Acronis True Image Home 2010 for these kinds of operations.

It is a great tool to have - you create a (linux based!) bootable media with a GUI-based application for making and restoring backup images of disks or partitions (including compression and skipping empty space). I also use the included Windows application to make incremental backups of my whole system, which I can restore to bare metal in case of a disk crash etc, or just recover single files if I need. It works great with external USB drives, saving disk images to FTP/CIFS share and so on.

I got the OEM version for free (bundled with my external Seagate drive), but buying it online is less than $50, and you can download a 30-day trial by clicking here, although the trial will only let you restore backups when booted from the rescue media, not create backup images. You should still be able to create the backup image from the windows app.

Edit:

Changed info about the trial version...

I've found with all the new PCs that I've purchased over the last couple of years that they either come with DVDs that allow the re-installation of original software (OS, programs and recovery partitions), or a utility pre-installed that allows me to create DVDs that do the same. Have a quick look through the installed applications for a utility that creates "factory restore" DVDs before looking for other solutions elsewhere.