1. You might try a different mechanic.

2. See if you can get your old starter back and have a starter shop test it.

3. Take the car to a good dealer, intermittant problems are often very hard to find, but sometimes a dealer can check a code (special equipment), has seen a bulletin on the problem (factory support), or has actually seen the problem before (luck).

Do a search on instrument lights, you might find something there, perhaps a bad ignition switch?
--
2 8s & 2 7s 600,000 miles total