£500 is quite realistic (excluding the monitor/TV/whatever display you want) for a complete small case unit, I think for a shuttle that might not be enough, but I haven’t checked their prices recently.
http://www.quietpc.com/uk/ have fanless PSUs, CPU coolers, case fans and in fact everything else quiet you would need to build a system.
http://www.quietpc.com/uk/htpc.php#htx00 have cases designed to blend in with AV equipment and be quiet with good airflow, but they are not cheap and you could save £100 by getting a small regular desktop case, provided you can find a style that suits you and it has good airflow.
http://www.zalmantech.com/ http://www.quietpc.com/uk/products.php have a wide range of quiet CPU fans, many UK retailers sell them also.
You can get a AGP graphics card with passive cooling and it won’t generate too much heat, they are only really under extreme stress when gaming, being used for a PVR they won’t contribute that much to case heat.
http://www.byopvr.com/ have many reviews of PVR software suites and tips for building a PVR
I don’t know if you would want XP Media Center Edition or just XP Pro or something else entirely. You should also probably look at getting some additional remote control units, most TV tuners etc come with one, and you can get windows plugin software that lets you control more of windows with it, but to be able to use windows properly you would be better off getting a separate unit. The alternative is a wireless keyboard and mouse with good range, but that’s not ideal.
I think this would be very fun to build, I don’t really have a use for one now (or the money) but if I did I would already have it underway I think.