So you want to 'Set Regarding' an activity to a contact who you canot see or select? To do this via the user interface, your user would need read privilege on the contact or have the contact be shared with them.
You could use a workflow to 'set regarding' the activity to a specific contact because so long as the workflow is owned by a user with higher privileges (i.e. a system admin), the workflow will run with the priviliges of that system admin user even though
triggered by your restricted user.
The downside is you would need a single workflow creating for each contact per activity type to which you want to attach activities to. If you only have a handful of these 'inaccessible contacts' then maybe it's an option.
Microsoft Certified Technology Specialist (CRM) GAP Consulting Ltd Microsoft Community Contributor Award 2011