Well I guess your status column has very low cardinality... how many distinct status do you have?
Your data is not distributed evenly, I just saw the number of rows returned, 4 out of half million.... if you generate histograms for that index most probably optimizer would use the index for that specific query. However if your application is using bind variables then histograms is useless....
Also by deleteing statistics is forcing using RULE optimizer
Try generate the histogram wth 20 hash buckets see if it uses optimizer, if not increase hash buckets to 40 and see
But are you sure your query is faster with RULE optimizer????