In the UK, you're looking at ~£50 for a short turnaround from a fab house like PCBTrain. From there a single small two-layer board, 50x60mm, 15 weekday turnaround is £33 plus shipping . It scales very well, but that's not the point for a prototype. Want that board this week? £90. Oshpark is great, but only if you can afford to wait the 20 or so days it takes to get to you.

If anyone can recommend a good, cheap fab house in the UK I'd be interested to know about it!

Perfboard is fine up to a point, but I find it tends to get messy, even for simple boards, and it's not terribly optimal with regard to space. You're out of luck (without bodging) if any component is surface mount or isn't 2.54mm pitch.

Milling is a nice stopgap when you need a single copy of a board that's a bit too complicated for perfboard (i.e. different pitch/smt parts) but isn't worth spending 10x the cost for a professionally made board. With milled boards you can have custom shapes, cutouts and so on. If you're trying to design a board to fit inside some housing with a funny shape and standoff points, milling the board to fit is a nice and cheap.