Your requirements are outside the limits of your mechanical equipment. It would be rare to find a solenoid that could open and close at that speed. The pulse circuit needs to be isolated with an OCI and the solenoid needs to stay on the edge of movement, voltage and current wise, if it will take that without overheating. You can then by means of your Ardunio apply a pulse to the OCI and cause the current to rapidly increase so that the solenoid completes it's closure cycle. The closing force required could also be less by applying a permanent magnetic field to the end of the coil instead of a current to the winding. An OCI would also allow the kind of current allowable to a prototyping board and the Ardunio. I have seen the magnet trick done in some industrial equipment. It may of course cause one of those unintentional side effects slowing the opening and producing an arc. That might be helped by action of a snubber. To get a sharper edge on the current waveform you might use a HEXFET instead the Bipolar transistor. That also reduces the current flowing on the switching side to almost zero and might close solenoid faster. As I said earlier I think the closing speed of the solenoid is your problem here. Since I don't know your current and application here I don't know what is possible for sure. You might also think about a solid state relay that leaves out the solenoid altogether. I am wondering if your biggest problem isn't the relay/solenoid arrangement.
I am new to Ardunio but have worked for over thirty years with industrial process controllers. I like the Ardunio if I can only get past the sparse information and learn to code. Oh for relay ladder logic.