You can switch tanks, hook up two tanks at once, or use a larger tank (refills are cheaper per lb with larger tanks).
The LP (liquid propane) does need to go from liquid to gas to go through the regulator. When you use the propane rapidly, it uses the heat that is in the propane to "boil", hence dropping the temperature of the surrounding liquid and tank. A larger surface area to evaporate the liquid from is the best cure for slow evaporation due to cold temps.