Suitable NMOS with 3.3V gate voltage to switch 12V 500mA
This isn't a shopping question, it is a question about using the digikey search and reading FET datasheets, so it shouldn't be closed IMO.

Usually a MOSFET datasheet will specify its guaranteed max RdsON at a specified Vgs or over a range of Vgs. This is from the one in your question:



Max RdsON is specified over a range of Vgs. This is important, when you drive a FET with a specific Vgs you must pick a part with  a RdsON spec at this Vgs (or lower Vgs). 

VgsTH spec is not useful for switching applications. At Vgs=VgsTH the FET only begins to conduct, but if you want it to be fully turned on you will need a higher Vgs... but the VgsTH spec does not say how much. If you pick a FET with VgsTH below 3V3 then it will turn on at Vgs=3V3 but you don't know what RdsON it will have at that drive voltage. It may turn on fully, or just a little. This is probably the reason why your FET does not work well.

On the other hand, you can be absolutely sure this FET will switch fine with 3V3 gate drive, because its max RdsON is specified at Vgs=2.5V.



The "drive voltage" field in DigiKey search engine specs "Drive Voltage (Max Rds On, Min Rds On)" which means this is the voltage range for which RdsON is guaranteed in the datasheet.

So I checked every "drive voltage" between 0.9 and 3V (use shift key to select a range) and got lots of choices. You'll want to refine that, select packages you want, sort by price or RdsON, etc.