FYI, I am not using the built-in PWM as eventually I will control about 10 LED strip lights independently with a single Arduino Uno. Since there aren't enough PWM pins I am doing this in software. In any case, as I see it the problem isn't really driving the gate of the p-channel MOSFET. Instead, it seems the voltage to the LED strip light is not going to ground fast enough.
You said that that below ~10V the LEDs are like an open circuit (each LED needs about 3V to turn on). So are you saying that once the voltage drops below 10V the LED goes completely off and I shouldn't worry that the drop off is slow anywhere below 3x3.3V=10V?
As for the probes, I don't think they have any significant influence. I can't see any difference in diming at all when they are connected of disconnected.