What about adding an indexed calculated field based on those 4 columns.  Than would make the range search much more simpler and it should be much more overhead on the server (not more than having to scan an index (not sure here but it seems that a scan is hard to avoid)).