Does encoding Namecoin/messages into the blockchain bloat it? I read today twice concerns about inflating the blockchain:


NameCoin
Bitcoin Message Service


So, does using these services "over inflate" the blockchain? The way I see it, if another protocl rides on top of Bitcoin but obeys by its rules and pay all the proper transaction fees / mining time, then it's "legit". My question is how can such a "legit" protocol inflate the blockchain more than a regular miner would?

Does it introduce spurious transactions? If this actually became a problem, wouldn't increasing the minimal transaction fee solve it?
NameCoin merged mining adds no more than 49 bytes to the size of the block.  Namecoin messages aren't stored in the bitcoin block chain, instead the hash of the most recent namecoin block is stored in the Bitcoin block providing continuity between a potential hash and the Namecoin block chain. 

So yes it technically does "bloat" the Bitcoin blockchain but it current is ~4% and that percentage will decline as transaction volume increases, as that fixed 49 bytes is measured against increasingly larger blocks.

As for "how" can it be done.  The coinbase transaction (which transfers rewards and fees to miner's address) contains a field called coinbase.  Without merged mining this field is used to generate entropy for hashing process (extra nonce) which alters the block header each time it is changed.  Allowing a miner to try nearly infinite number of hashes. 

This field is not used by the blockchain for anything other than entropy so adding namecoin hash to the field doesn't collide with any Bitcoin transaction.  Once a block is signed the field is never used for anything other than verifying the block valid (by verifying the hash is correct and is smaller than required target).