The best somewhat unrestricted proto deal I have found was also Advance Circuits (4pcb.com) with the $33 deal. While it used to be a min. of 3 boards but now it is 4. They don't restrict you on drill sizes and provide a pretty decent size limit on the board dims. If you are fairly confident in your design, it sure beats point to point or wire wrapping.
They also have a bare bones deal which gives you another really cheap option in less than a week.