The 2222 is a bit small for this. Its really a small signal general purpose NPN.
For a 500mA collector current, beta might be as low as 10, meaning you have poke 50mA into its base to get it to turn on properly. Which the moteino cannot supply. There are better choices.
There are lots of NFETS that would turn on to a lower on resistance, and not need to waste base current. Choose anything rated for 1 or more amps of drain current, and logic level gate drive. They will switch this load reliably.
And yes, that catch diode across the solenoid is a really good idea. If you expect the transistor to turn off again. More important for a bipolar than a DMOS.