What's the extra CPU cost for recovering the public key?  Current bottleneck for bitcoin transaction processing is the CPU cost of ECDSA signature verification, not disk space or bandwidth, so saving bytes at the expense of more CPU is not the right thing to do.

There is some extra CPU cost certainly. If the goal is to reduce the CPU cost of transaction processing then there are other low-hanging fruit to pick beforehand.

• Change the software so that not all clients have to check all signatures. This was raised in http://bt.irlbtc.com/view/6373.msg94314#msg94314 in the context of speeding transaction propagation.
• Use a smaller curve - 256 bits is very conservative
• Use a different group with faster operations like curve25519
• Remove the incentive for generating lots of transactions

Not recording the public key in the scriptSig would be a breaking change and so there are many other improvements we could apply at the same time.

ByteCoin

A suggestion: introduce an additional OP_GENPUBKEY, which pops a signature and a 2-bit number from the stack (which states which of the 4 possible generated keys is the right one), and pushes the generated public key (for this transaction and signature) itself onto the stack. From then on, it can be processed by the existing infrastructure, such as checking it against a known value, or first hashing it using OP_HASH160 before comparing it to an address.

A typical scriptPubKey for consuming a spend-to-address would then become:

  OP_GENPUBKEY OP_HASH160 <address> OP_EQUALVERIFY

With corresponding scriptSig:

  <signature> <generatedId>

If we drop the DER-encoding of the signature and just give the 2 256-bit numbers, prefixed with a version byte maybe, this is a 24-byte scriptPubKey, and a 67-byte scriptSig (compared to a 25-byte scriptPubKey and a 139-byte scriptSig now)

As suggested by [mike], we could go for an even smaller but slightly less flexible OP_CHECKSPEND, that does everything:

  <address> OP_CHECKSPEND

Which is only 22 bytes. We could do without the generatedId (allowing a 66-byte scriptSig) in this case, but at a potentially increased verification cost (2 to 4 possible pubkeys need to be verified).

I believe that transactions are verified when they are received before they are relayed. When a block is received, all the transactions in it are also checked before the block is relayed even though most of the transactions in the block have already been verified in the process of relaying them to the miner.

ByteCoin

Patch is here: https://github.com/sipa/bitcoin/commit/6e223c405988a1002eeeee69db88a1128a38b0a3

Revisting this topic.   While changing the protocol to allow transactions with implicit public key recovery is worthwhile it would be a breaking change so I understand not moving on this.  However there is absolutely no reason for the Bitcoin-Core client to require an address when verifying the signature.  The PubKey can be recovered from the signature the PubKeyHash produced from that and then the address generated from that.  

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?
I would add the UI in the core client for this section is not user friendly.  A user verifying signature has to copy and paste three separate components into three different boxes (one of which is pointless).  How about a unified copy and paste of a single signed message block?
Why not have the user supply the message & signature (preferably in a unified encoded form (i.e. similar to PGP signed message) and then the client verifies the signature and computes and displays the results?

An example which puts it all together.

Input

and the client responds with either
Message verified to be signed by 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

or

Message not verified.  Please double check signed message is copied in it entirety including the BEGIN and END lines.


Brainwallet.org has something similar and is more intuitive than the Bitcoin Core client.  Still even the brainwallet website adds a "warning" that is pointless and vague.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T (but address was not found in the signature!)

The address is not found in the signature?  Is that bad?  Should I be worried?  Am I being scammed?  To most users, yellow is a color of caution.   The expected outcome would be a definitive "SUCCESS" (and green) but instead there is this ambiguous partial success.  The "yellow" response is pointless as anyone can add the address in after the signature is created to remove the warning.  So what is is warning about.  Adding the address 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T just above the signature looks like this and provides the expected "good" response.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

The "caution" response only undermines the point of even allowing signatures that don't include the (unnecessary) address.  Imagine you are a company which sends out signed messages to customers.   Lets use the 80/20 rule.  If you exclude the address 80% of your users will understand the "warning" is pointless however that means you are going to confuse 20% of your customers and that means extra cost and work.  So why not just include the (pointless) address so it shows up as green.

Still the behavior isn't as bad as the core client which refuses to validate the signatures and throws an error.

I can see that as a valid point, I just wonder how much security it really adds.  Unless user already has the address in the wallet ahead of time or gets the address out of band it is very likely they are copying and pasting the signature as provided by the signer (potentially an attacker).  In a case like that the attacker could provide the user the "spoofed" (technically similar) address and most users will copy and paste it along with the other components and get a "good" response.  I think showing the computed address and an explanation (maybe a "what does this mean? link) would do more to prevent social engineering type attacks.  A user controlled preference would be nice, Bitcoin-Core is targeting power users.

Still lets put that aside, a unified signed message block containing the message and signature ("PGP style") should be pretty straightforward.  It would help reduce issues with trailing spaces and copying errors.  Is there a reason that Base64 is used over Base58? One reason Satoshi outlined for using Bas58 over Base64 is that it can be easily copied, try double clicking to copy each of these two signatures.

Stupid forum software inserted html span code into sequence.  I put it into a code box so it should illustrate it better now.