The Problem

When a user that is restricted from a specific list visits the site; the view of that list displays an access denied message rather than hiding the Web Part from the user.  It appears that the security for the list is evaluated prior to the Web Part evaluating the targeted audiences.  Since the user does not have access to the list, the access denied message is shown as a result.

The Solution

We can remedy this issue by granting the lowest privilege on the list for the user.  As a requirement, the user must not be able to view any list items, so we will give the user the ability to see the list, but not the ability to see any items in the list. This is accomplished by creating a custom permission level that will contain ONLY the Open permission from the Site permissions group.  This will allow users possesing this permission to open the list, but will not grant them the permission to open any items in the list.  Grant the newly created permission level to the restricted users on the list and the audience targeting on the list views will now function as intended.