What about linking them to the miniboss rooms? Have one of the sides be bombable (without any other outward indications) to reveal the door. With a normal miniboss room, there are 4 door locations, with 2 leading to other rooms. This would leave 2 locations open to having the secret room. At the beginning when there is only 1 miniboss per floor, it would be rather easy to find the right location, but on higher floors with multiple minibosses it becomes somewhat harder, providing a nice natural difficulty increase. At the same time, the increased variability of missile ammo on earlier floors due to having generally less rooms makes sure that getting to the secret room isn't always a no brainer.
It also provides players an additional reason to enter miniboss rooms when they might not otherwise. For instance, I sometimes avoid miniboss rooms until the end to make sure I'm as strong as possible and I don't have any problems dealing with whatever's inside; but if I were really struggling, I could see myself deciding to go for the miniboss in the hopes of getting a good secret room item.