The Text vs. Interpretation
Remember that earlier editions of D&D don't have the years of playtest experience under their belt to tell them they need to be very explicit on what a spell does. Earlier editions of D&D instead relied on DM interpretation. You mention that you were told thisthat some creatures, a Kraken for instance, might be partially or fully immune to Hold Monster, but that would depend on the interpretation that a Kraken is not a creature, since the Hold Monster spell states that it holds creatures.
Depends on Size
Area of Effect: 1-4 creatures in a 40-ft. cube
The text of the spell doesn't mention a limitation on type of creature, but it mentions that you can hold up to 4 creatures within a 40 ft cube. Hence, this might be interpreted that a krakenKraken, which might be larger than 40 ft cube, might be immune. This is largely open to DM interpretation, and a DM may determine that "within a 40 ft. cube" means the monster needs to fit inside the 40 ft. cube, or that the up to 4 creatures held must all be within a 40 ft. cube (or, presumably, both). This interpretation supports the idea that a kraken'sKraken's body, dependent on size, could be held, while the tentacles, which are outside the 40 ft. cube are not held. Or, vice versa depending on the location of the 40 ft. cube.
Multiple Hold Spells
There is, however, an explicit difference between things you can hold with one type of Hold spell that you can't hold with another. Hold Person holds persons (bipedal human, demihuman or humanoid), Hold Monster holds monsters/creatures, and Hold Undead holds undead. I realize you're talking about different types of monsters, not other types of being, but it illustrates the intent behind the Hold Monster spell that they felt the need to explicitly call out other types of beings in other Hold spells. In other words, if your creature meets the qualifications of the spell (e.g. is a creature, and fits inside a 40 ft. cube you can see within your level * 5 yds) you can try to hold it with the Hold Monster spell.