This probably sounds pretty dumb, but wouldn't algae blooms produce a lot of oxygen? Although they would die out and decomposers would use up oxygen, is that more than what the algae produced?
Algae produce O2 in the upper layer of water but when they die they stop producing O2. They sink to the seafloor and most get decomposed by bacteria on the seafloor. In this process, bacteria use O2 contained in the bottom layer of water which decreases the dissolved O2 concentration in the bottom water.
These concepts (and much more!) are well described in the excellent open-access paper by Rabalais et al. (2010) Dynamics and distribution of natural and human-caused hypoxia. It also includes case-studies of areas affected by hypoxia and eutrophication around the world. A must read if you're interested in this topic!
As you surmise, the oxygen is consumed by decomposers. From the Wikipedia page on Eutrophication:
Phosphorus is a necessary nutrient for plants to live, and is the limiting factor for plant growth in many freshwater ecosystems. The addition of phosphorus increases algal growth, but not all phosphates actually feed algae. These algae assimilate the other necessary nutrients needed for plants and animals. When algae die they sink to the bottom where they are decomposed and the nutrients contained in organic matter are converted into inorganic form by bacteria. The decomposition process uses oxygen and deprives the deeper waters of oxygen which can kill fish and other organisms.