Curiously, a SIM can enforce bookmarks and contacts on a new iPhone- but they're certainly deletable.

A sim can have contacts, but bookmarks? Are you sure?

I just put in Italian Vodafone SIM into unlocked iPhone 4S with iOS 7 and got Vodafone bookmark in Safari, which is indeed deletable. Haven't noticed new contacts so far.

It's not the SIM, it's the carrier bundle. Each iPhone ships (and updates) some XML files for each operator that contain all specific operator settings. These vary from radio configurations to features lock/unlock; eg: you can tell the iPhone how to remote-check whether tethering is activated on the data plan, and change the UI accordingly; it can also contain a custom action box to show to the user when they try to activate the feature, and/or activate the feature itself directly, communicating to the operator network so that they can bill the user.

Carrier bundles also allow carriers to specify bookmarks to add to Safari, the idea being that users "might find useful" to have direct links to check their invoices or so. Such bookmarks are of course deletable.

Yep, it's the carrier bundle. I have an unlocked Canadian iPhone 5 and when I put a T-moble sim in when travelling to the USA, I get an entry in my stocks app for T-moble.

That very specific thing? No.

Or the more general case of allowing carriers to mandate restrictions that Apple do certain things that provide a poorer experience? Of course.