My suggestions:
- Don't use exhaustive search - it does a pixel by pixel comparison and is totally unnecessary.  Adds a LOT to encoding time, and has very little effect on size in general
- Use 2 reference frames (shame you can't use more)
- Don't use HE-AAC on the PSP - it doesn't support SBR, so it'll end up sounding worse.  I'd use LC-AAC, VBR @ q0.2 or similar.
- I'd probably use constant quality over constant quantizer, but that's a bit of a choice to you

The main things you optimise are ME algorithm (use multi-hex) and SubME (use level 6 or 7).