Holodecks and replicators don't appear to be particularly energy-hungry in relation to important things such as warp drives or shields. They are literally household technologies, after all...
OTOH, household technologies today tend to be optimized more than military ones on issues of energy consumption, if only to fool "environmentally conscious" consumers. The holodeck might well be smart enough to recycle materials extensively, and to minimize replication expenses by substituting cheaper holographic items in place of real, replicated ones whenever possible. It might well be more energy-expensive to run life support for Deck 11 than to run daily holodeck sessions on that deck.
On the issue of deuterium shortages, and more specifically the only known case of those, VOY "Demon", the stock answer is that deuterium is ubiquitous - but the smart user only gets it where it's really cheap, that is, already concentrated and purified. Which means that said smart user can indeed run out of it if stretching the last drop too long in an attempt to find an ideal refueling spot. It might well consume 15 units of deuterium to collect 1 unit in an average star system, and 150 units to collect 1 in empty space; one would have to find a planet with enriched deuterium (essentially, a waterworld would be nice if you can't find an industrialized location) to get more than 1 unit per 1 unit spent.
They pick it up as they go from the Bussards.
This is never canonically established. More probably, the Bussards only scoop hydrogen at very special locations, such as the atmospheres of suitable gas giants, and are useless in deep space.
You'd have to assume the antimatter was naturally occurring as well, since making it from scratch would take more energy than they would get.
Not really. The amount of energy is irrelevant as such: the universe is full of energy, but most of it is in useless forms. If you can spend 2,000 units of a not particularly useful type of energy (such as dull old deuterium) for creating / converting / unearthing / etc. 1 unit of more useful type of energy (such as the densely packed wonderfuel antideuterium), you should probably do it. Antimatter can release energy fast enough to drive your starship; the deuterium you used for making that antimatter could not have performed that task (because fusion gives out less power than annihilation), but it did prove useful in creating the antimatter!
This is why it's practical to burn lots of crude oil in order to distill jet fuel for your fighters: the jets couldn't burn the crude oil no matter what. This is also why it's practical to burn lots of crude oil to charge your flashlight batteries, because crude oil is not a good source of portable illumination... Fusing deuterium to create antimatter is not fundamentally different from running an oil-burning powerplant to charge your Maglite.
Timo Saloniemi