There are some points, that can't be clearly seen from your post:
- is the relay contact rating sufficient for the solenoid current?
- can you determine if the relay is acting without any delay
Assuming that the relay is working correctly, your original setup without a diode will result in fast current decay, although some contact arcing occurs, which can reduce the contact lifetime. Placing a diode accross the solenoid coil suppresses arcing but increases the current decay time slightly. The fact that you don't observe a difference between both cases suggests, that the problem hasn't to do with current decay. Nevertheless, fast current decay without strong current arcing would be achieved by allowing a inductive kick-back voltage of the coil of a few 10 volts, using a varistor or a z-diode + rectifier diode combination, as already suggested.
To check, if the solenoid itself is acting fast, you can also check the behaviour when disconnecting a wire.
If curent decay isn't the problem, I mainly suspect inertia of your mechanical setup. Besides changing the design, adding a return spring may be helpful.
I also mentioned magnetic remanence as a possible problem. The solenoid yoke can be expected to be made from magnetically soft iron and not affected by remanence. Using hard steel for the pallet (the coil core) wouldn't be optimal, not necessarily cause a slow release. Applying an oppsosite current pulse of reduced magnitude to reset remanence requires a reverse of polarity and can't be assured to be effective. A return spring would also help in this case.