I have a list that contains just over 5000 items, and it is triggering the List View Threshold message for non-admins.

I can easily make the error go away by increasing the threshold as has been suggested in numerous forums and blogs, BUT THIS IS NOT A LONG-TERM SOLUTION so please DO NOT suggest changing throttling settings as a solution. My PREFERRED solution is to use indexes and filters (NOT increasing the threshold, using folders, or other approaches suggested by Microsoft.

SO... I have created an INDEX on one of the columns (which is a Lookup column that has about 10 possible values). The default view is configured to filter based using the column that has been indexed. There is no sorting; there are no other filters; there is no grouping; all other view settings are default. The view returns around 500 records (paged at 30 record intervals) when using Administrator credentials, but I get standard message "This view cannot be displayed because it exceeds the list view threshold (5000 items) enforced by the administrator" when using non-admin credentials.

It could be worth noting that I added the new index only after the list exceeded the 5000 item limit. As a test I also tried the following (didn't make a difference): remove the index, increase the threshold to 10000 items, and then re-add the index.

More testing: I have discovered that if I create indexes and corresponding views on Number-, Date-, or Single-line-of-text-type columns then the error goes away for my non-admin test user. Index/view combinations based on any Lookup-type column in my list does NOT work.

Everything I have read in forums, blogs, and MS documentation suggests that what I have done should be working, but no luck. Any help is appreciated. 

Is the Indexed Lookup column single valued?  Are you loading any additional columns along with the primary value of the Lookup column?