Homemade PMOS LDO again, is a few millivolts of oscillation normal?
You've got a number of problems, and I'm not sure which one of them is biting you on the butt.

1) You don't show the entire connection for the TL431, but I assume that you've tied the reference input to the cathode so as to get 2.5 volts. Please check the data sheet http://www.ti.com/lit/ds/symlink/tl431.pdf, figure 17. You must get rid of C1.

2) The fact that you needed a pullup resistor on the gate of your MOSFET should have told you something, and that something is that you need a different op amp. The TL081 is nowhere near a rail-to-rail output device. If you look at the output voltage swing figures you'll see that for +/- 5 volts, you can only count on ~+/- 3 volts when driving a 2k load. In your case, it means that without help you can't produce a high enough gate voltage to turn the MOSFET entirely off. When you say "if the pullup resistor is large enough, e.g. 20k", I assume you mean "if the pullup resistor is small enough, e.g. less than 20k".

Plus, you haven't mentioned the output voltage from this regulator, so I'm assuming 5 or 6 volts. This in turn suggests that your input voltage to the op amp is in the neighborhood of 1 volt. This is well outside the input common-mode range. You can try changing R4 to 1k and trying for 5 volts. This will let the op amp inputs run at about 2.5 volts, and that may make a difference.

Finallly, the gate capacitance of the MOSFET is listed as 3400 pF. Combined with the fact that you're at the hairy edge of what the op amp can drive, I wouldn't be surprised if this is a problem. Op amps typically have limited ability to drive capacitive loads while maintaining stability.