Lookup table user permissions

What I want is for a given user to only be able to see their own records. The permissions page should allow me to do this by choosing "Allow users only to see their own data".
This works well, except for lookup menus. Users can see + select anybody elses data from the menu.
Is there any way to work around this issue?
It seems like a custom where clause would be the best solution, but if I do that the "Add New" button cannot be enabled, and this makes the system awkward to use.
Thanks!