I would also start by disassembling and cleaning the burner of any rust and scale, and making sure the venturi is clear of spider webs, and mud dobber nests.
When it's lit does the flame burn a clean blue color, and leaves no soot? If its yellow or orange and leaves soot, then your not getting a good air/fuel mix. A leaner fuel mix will burn hotter, and cleaner.
Both Juthro and majormillet are right on the money. Its almost always the burner assembly. I just dealt with this problem last night with a crab ring. The burner was so rusted to hell it was beyond saving. Couldn't even disassemble it for cleaning it was so rusty.
Most propane regulators that come with bbqs are factory set ( at 10PSI I think, it should be printed on the regulator). The parts responsible for what pressure you are getting are enclosed in the regulator so unless its been sitting out in the rain or has been getting dropped pretty hard its very unlikely that is your problem.
You can get adjustable regulators (look for hose fittings stores in your local industrial area) but your decrease in performance is much more likely due to the burners/air intakes plugging up with rust/charred stuff.
I'd check the o-ring on the fitting that attaches to your propane tank (the one that connects to the BBQ itself is usually a metal-metal gas tight fitting. No o-ring required) while you are at it. Its not the source of your problem but if the rubber is starting to degrade you'll want to replace it.