Would a Helium powered balloon vehicle work on Mars?

I doubt that this is feasible at all. The atmosphere consists mainly of CO$_2$, which is heavier than helium but the absolute pressure is only 0.006 times our standard pressure. So basically the helium vessel would be lighter but the total force due to the buoyancy is tiny compared to gravity which is only 0.4 times less than on earth.

Just try to calculate the volume necessary to lift 1 kg.

As Dan Piponi pointed out there are some really large ballons from NASA. So if we take those dimensions of the linked article with 22 million cubic foot at 110000 ft to lift a large science experiment my estimate is that one needs approximately 400 of these gas bottles (with a pressure of 200 bar each):

So that seems not feasible for any kind of Mars exploration in the near future.

Edit: As the necessary amount of helium scales linearly with the weight this depends a lot on the scale of the craft. The Mars Global Surveyor with 1035 kg would require the mentioned 400 gas bottles, even more for larger probes such as the Mars Reconnaissance Orbiter (2180 kg). A small sensor package, essentially a nanosatellite (1-10 kg), is feasible, as the required amount of gas is orders of magnitude lower.

1. Yes, a helium balloon can certainly work on Mars. There have been many studies at NASA's Jet Propulsion Laboratory and NASA's Wallops Flight Facility that show feasible mission designs. Solar-heated Montgolfier balloons may provide more lift for the same total system mass, but have very large altitude variations, usually touching down at night. A super-pressure helium balloon provides much better stability for long-duration missions. Both such systems are discussed in this paper. (Side note: a system to keep Helium in the liquid state would very likely be more mass than just high-pressure tanks to hold the same amount of compressed Helium.)

2. Why would you want to recompress the Helium?

3. Using a balloon for terminal descent purely to avoid a parachute and rockets would be mass inefficient. You need a very large balloon for a small payload mass. However it has been proposed for very small payloads. (See above paper.)

4. A balloon on Mars is useful for payloads that want to be above the surface but not very far, and then want mobility across the surface. What is really needed is a mission that needs a balloon, not a balloon that needs a mission. One common example is a magnetometer mission to map magnetic fields. Since the magnetic fields drop as a high power of radius, the sensitivity is much greater at balloon altitudes than at orbital altitudes.

About question 1. Yes it is possible to have to have working balloon on Mars, but there are couple important differences:

1. pressure of atmosphere on Mars is 0,7-0,9 kPa comparing to 101,325 kPa on Earth it’s very low. This means that density of atmosphere is much lower and lift given by balloon is also much lower (this reduces effectiveness of balloon by more than 100 times).
2. atmosphere components are different on Mars, 95,32% is carbon dioxide. On Earth nitrogen (78,084%) and oxygen (20,946%) are leading components. This increases density of Mars atmosphere about 40% and improves lift of balloon.
3. since Mars atmosphere doesn't contain oxygen (0,13%) it would be better to use hydrogen (it is 2x lighter). On Mars it gives only 1.05 times better lift than helium but hydrogen is cheaper and easier to maintain. On Earth we don't use it since it is dangerous with oxygen, see Hindenburg.
4. Surface gravity is unimportant (see Archimedes' principle)

Using hydrogen you need 100/1.5/1.05 ~ 63 times more gas (in balloon diameter it means 4 bigger) than on Earth to lift same weight. If you ever seen balloon then you know that it is not practical idea.

About question 3. See Mars pathfinder. It is not exactly balloon but you can see that they were thinking about that. During atmosphere entry full size balloon (which would allow floating) wouldn't be able to survive extreme conditions even if you use best materials. Even if it would be possible to have such materials then wind pressure will compress balloon to unpredictable shape leading to disaster.