Using bitcoind v0.9.0rc2-17-gd33f69a-beta (64-bit). When using bitcoinj as a client to to retrieve blocks from bitcoind with the wire protocol recent blocks were able to be retrieved as normal but when starting at the genesis block invalid blocks were being returned.
The following steps were taken: 1/ complete ver/verack handshake 2/ send getblocks message using genesis block hash as the locator 3/ receive inv message with 500 block hashes. The first 5 were manually validated as correct by checking blockchain.info 4/ send getblocks message using the same inventory items from the previous inv message. 5/ 500 block messages returned by bitcoind. However every block 81 bytes long. First byte was 0x02 (which is the wrong version for the genesis block) followed by 80 0x00 bytes.
After much investigating it turns out blk00000.dat was missing. Apparently rather than failing when unable to locate the block in the blockchain bitcoind was returning zeroed arrays of bytes. Whilst a peer could probably recover from connecting to a bitcoind in this state as it will simply ignore the obviously invalid blocks it's not quite the behaviour you'd expect. The client behaved completely normally as a client. Guessing it would have continued to do so unless the wallet contained outputs from the missing blkxxxxx.dat.
Unable to pinpoint when the file was deleted but likely it was several weeks ago and the client has been running happilly without it.
Presumably the indexes where still present as the bitcoind was able to produce a valid inv response to getblocks.