I was starting to think down this road myself recently, and had some thoughts about starting back at the simplest solutions an wondering why they weren't effective:

Namely, for the situation of a paper wallet or physical object (coin, etc.) being created by someone else, why not use a HMAC_SHA256 function? That would look something like:

Client picks a password p and a salt S. Using HMAC_SHA256, with p as the key, signing the message S, an output hash k of 256-bit length then becomes a private key for a Bitcoin address. The Client derives the public address K, and sends S and K to the printer to be printed onto the physical wallet. When the client receives the (amazingly gorgeous!) wallet back, they can add p to it before storing it safely, ensuring anyone who was in possession of it could easily derive k from p and S, or leaving p a secret, making it a "brainwallet" that only the client could unlock.

Variables summary:

• p Private password picked by client
  
• S Private salt, shared with wallet creator
  
• k Address private key, derived from p and S
  
• K Public address of k
  

This would be vulnerable to brute-force attack by the wallet printer (they need to crack p since they know S), or in the case of a paper wallet where S is secret (covered by hologram or inside the physical coin), someone holding that paper wallet would need to crack S since p is visible on the wallet. Meaning the strength of p and S would need to be rather strong.

So, to prevent people from picking "puppies" as their password p, what about employing BIP39 for this? Make both p and S a random 128-bit number, which commonly is expressed in mnemonic form of 12 words. 128 bits is 16 bytes, which is 32 characters long expressed in Hex, which fits nicely in a 3-Q QR code (Version 3; 29x29 cells, Q-level error correction; 25% error recovery). The wallet can have a QR code for S and/or its mnemonic or base58-encoded, both optionally covered by a hologram by the printer. The client then can print the mnemonic of p on it, as above. 128-bits is the same strength as BIP32 and Electrum chain codes, which should be strong enough on their own, to resist a brute-force attack.

Alternately, make the bit-length of p and S smaller, and use Scrypt on the HMAC_SHA256 to ensure brute-forcing is still hard. If p and S were 64-bit, that would be a six-word mnemonic, 16 hex characters (fits in a 1-Q QR code; 21x21 cells), or 11 base58 characters. Would Scrypt parameters of something like r=8, p=1, N=1024 be a good starting point?

So, from your list of requirements, thinking S is really the "minikey" in this scheme:

• 30-character code that starts with P (so, 29 random characters): No, this would be identifiable as a two-part key, both halves presented as a BIP39 (or similar) mnemonic.
• The ability for a person to create the minikeys without knowing the password: Unlike the current minikey scheme, this one doesn't require "mining" for one, but the creator only has half the key required to get k
• Uses scrypt for hashing the password and deriving the private key: Yes.
• Tunable scrypt parameters: Yes. The Scrypt calculation would be done by the client before requesting the wallet be created/printed, so could be whatever they want.
• The ability for the costly scrypt step to be outsourced: No.
• Typo detection on the password, that requires all the expensive computation to be done to know whether the check passes or fails: Yes to typo detection (BIP39 has a checksum feature), no to expensive.
• About 169 bits, 156 of it random: Two 64-bit half-keys would only be 128 bits of entropy, but that could be adjusted higher.
  

So, not a perfect match to your requirements, but very simple. The one other downside to this method is that if the client wants dozens of wallets created, they need to pre-calculate all them in advance (unlike, say the BIP38 using EC multiplication and a sequence of multiple addresses). As far as evaluating your requirements, I don't value the "outsourcing the Scrypt generation" as highly. I do think this simple schema could be improved by adding in metadata to indicate the Scrypt parameters used (as part of p) and a flag as part of S to indicate it is half a key (starting with some flag, like the 'P' you proposed; making S best expressed in base58 rather than mnemonic), needing some p to complete (and some hash/checksum of p to pair them back up if separated). Having 156-bits of entropy I think is okay; I think it should be somewhere in the range of 128-160 bits (if 128-bits is okay for an Electrum/BIP32 chain code, I'd set that as the bottom limit).

Any glaring holes with this rather simple option?