Hi,
UPDATE 2: Just found the following snippet on the internet. Text is lifted from a Google translation of the Telefonica (O2 parent) website.
Let us start with the confirmations. Tethering and MMS or "share internet" supported from day one. The "internet sharing is a feature included in the price data and therefore is not considered an extra service or pay more for it. This is important because the iPhone is a 3G modem and fantastic for this use is more than interesting.
O_O
Comments....anyone???
It's completely irrelevant what Telefonica do. They might be O2's parent company but this is in a different country with different tariffs.
O2 have clearly stated policies with regard to tethering and these were in place when you signed up to the contract. If you're not happy then the only solution is to not renew your contract when it's up.