A pilot operated valve (often unfortunately generalized as a solenoid valve"solenoid valve") uses a small control solenoid valve and the pressure differential across the valve to open a diaphragm that allows flow to pass. This is a very common design because it allows for a large flow to be controlled with very little energy. This YouTube video has a good diagram. Pilot operated valves have the limitation of only being able to shut off flow one direction and like you noticed they require a pressure above vacuum to stop flow.
This site on vacuum valves mentions that they can be used for high flow vacuum applications, but there are some limitations. So depending on what vacuum pressures you are trying to achieve, these valves may be an option. In your testing you may have just had the direction backwards. It may also not have worked because your applications requires blocking flow in both directions, this could be mitigated with a check valve if needed.
What you are looking for is called a "direct acting solenoid valve". This valve simply uses an electric coil called the solenoid, a ferrous plunger, and rubber seal around a hole. Most also use a spring to hold it in an off position, and the magnetic force overcomes the spring when powered giving two discrete states. The smaller orifice limits flow more than the pilot operated valves, but it is a simply on/off with less mechanical complexities. They can also operate in full vacuum. Some may still have a preferential flow direction, but most will be rated for full differential holding pressure in either direction. They can be Normally Closed NC, Normally Open NO, or some fancy ones have latching functionality like Mahendra Gunawardena mentioned.