Could this alternative hash based MAC construction be as, or even more secure than an HMAC? Begin hashing (Key||Message) 
Encrypt the hash state (or some part of it, such as the first 128 or 256 bits), with the key.
Add the encrypted hash state to the hash and return the result.


This could be roughly described as Hash(Key||Message||Encrypt(Previous hash state))

There are several properties about this:


It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).
Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).
A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.


(Also consider a “weaker” version where stage (1) only performs Hash(Message), [i.e. without the key])

[Non-expert alert: I’m not a cryptographer or even a computer-scientist, so I don’t have the knowledge or capacity for the type of percise mathemtical reasoning that’s needed to analyze this. I guess that’s why I’m asking it here..]
Security

The level of security is likely to depend on the cryptographic primitives - the actual hash function and cipher - used. It is very likely that you can construct a function that is insecure, e.g. where the cipher is used for both the hash function an encryption. So you need to prove that the hash function and the encryption primitive are not influencing the security, even though they are using the same key. It is much easier to use a single PRF or PRP and prove that secure. Using one function also greatly simplifies implementations.

Implementation issues

An implementation issue is that intermediate hash states are often not defined or clear. SHA-1 and SHA-2 do have "logical" intermediate states after a block is hashed as the hash output is basically (part of the) final state. The final state for these hash functions does not significantly differ from the intermediate state. This is not obvious for other hash functions. This is for instance the case for Keccak - the winner of the SHA-3 contest - as well as most other SHA-3 candidates. Using an intermediate hash state should therefore be avoided.

Expected properties

I'll iterate over the expected properties in order:


  It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).


Usually performance is less of an issue for shorter messages. I would argue that it is only faster for shorter messages; the effect on larger messages will be negligible. Even then, it would require the cipher implementation to be cached (and in the case of e.g. Java, optimized) in addition to the hash function.


  Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).


A hash function especially within HMAC already provides very good security guarantees. It remains to be seen if using a PRP would have any advantages; I would expect it to be less secure.


  A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.


One of the more annoying aspects of CBC based MAC's is the non-variable key size. This is for instance rather annoying when using the MAC as building block for a key derivation function (KDF). So this is - in my opinion - a significant limitation.

CPU hash acceleration

Note that there are also CPU level optimizations for hash functions. Well known ones live in the Intel SHA extensions, the VIA padlock security suite, the Sun Ultra-Sparks...