My concern is with governments or regulatory agencies forcing you to add notes.

Perhaps. The main difference, however, is that fiat stamping would be much more difficult to enforce considering there isn't a public ledger to verify your compliance.  Also, the existence of larger merchants with publicly known addresses would greatly reduce the foul play you described. These merchants would be the first to comply, with the smaller "honest" merchants eventually falling in line. A slippery slope for sure, but definitely a point of weakness in the decentralized nature of the network.

I haven't really seen this discussed, but wouldn't the ability to add notes to transactions become a privacy concern and a method of easy regulation? I'm imagining merchants being required to reply to payments with "receipt" transactions with notes that could potentially contain sensitive information (i.e. what was payed for, the receiver's mailing address, etc. Even a simple order number could be enough to connect an address to a personal identity.) Am I just being paranoid?