The ArcMap 10.1 functionality matrix shows that that North American, European, and World Places online locators are included in the functionality of ArcMap with no mention of a subscription being a requirement. The 10.1 product allowed batch geocoding using these services without restriction, or notification upon use that a subscription was required to use them in this manner. If this was somehow against the terms of use for the original 10.1 product your software should have prohibited its use.
A service pack, in my opinion, is not a new version release and these locators should still retain the same geocoding functionality that existed in the original 10.1 product. The annual subscription you now require is more expensive than the ArcView product itself! Many users do not need the entire feature set of the ArcGIS Online subscription. Users simply want to be able to do what we could before SP1, and if they had a need for the rest of the feature set of ArcGIS Online they would have purchased it already.