Proofing is hard to do well on a small budget. An inexpensive color laser won't give color-accurate proofs for anything other than itself. An inkjet may be expensive per copy, but unless you have a need to produce several proofs per day, it is a less-expensive alternative than a high-end (Fiery-driven, Postscript-aware) laser or a Xerox Phaser (solid wax, highly prized in the graphics industry for its color accuracy).
What's best for you comes down to volume, the output you're proofing for, and the degree of accuracy you need. Offset printing using using standard process inks lays color on the paper differently than an inkjet or laser printer. Papers vary in reflectiveness, absorption, texture and color, all of which have an effect on the appearance of the final product. There is no proofing printer in existence that can account for all of these variables. In particular, there are many papers used in offset work that can't be used in a laser printer (they scorch, curl, or shed particles from the paper surface), and some laser-compatible papers that don't work well on a press.
As a matter of personal taste, I dislike the appearance of even the highest-quality laser printing. It can be useful and economical for low to medium volume production work, such as in-house document production in a medium to large business, but I wouldn't go to that kind of expense simply for proofing except in a situation like Philip's, where multiple designers can proof to the same printer.
For low volume applications, where you are concerned only with color accuracy, your best bet is to use a good quality inkjet and calibrate it (and your monitor) carefully with a small selection of papers. In my own work, I use a wide-gamut 8-color inkjet (a Canon Pro9000) that prints up to A3 size, and only two proofing papers, one gloss and one matte. I don't worry about the cost of ink or paper because, frankly, the benefits far outweigh the expense.
This still doesn't guarantee accuracy for jobs involving Pantone solid inks, however. No inkjet can duplicate metallics or fluorescents, but some regular Pantone solids will be outside the gamut of any given inkjet printer. The same is true of laser printers, no matter how "high end" they are.
When you need extreme accuracy, get a proof from the print provider, and get the client to sign off on it. This is called a "contract proof" because it forms part of the contract with the printer, who is now obligated to provide final output that exact matches the signed proof. In the case of specialty inks, ask for an "ink draw-down" -- a sample of the actual ink on the paper that will be used to print the job. In such a case, you and/or the client's art director will also want to be at the press when the job is run to verify that the job is run accurately.