What often happens with partitioning is that, as part of the partitioning process, the table clustering is changed to be on date rather than some other column, such as identity. ...

900 columns is not per se an issue.

But this particular table could have been and should have been further normalized.

You've made the mistake of assuming that...

That query doesn't make sense.  You're doing an inner join based on "CompanyNids", so the values have to be equal for matching rows to be selected.  But then you're setting...

With that many variables in the query, I'd think you want to use the RECOMPILE option:
OPTION (RECOMPILE)
I don't think the OPTIMIZE clause would then be relevant, but you...

INSERT INTO BANDALLOCATION
  (BANDSYSID,ZONEID,RATETYPE,SIMPLEBREAKSINDICATOR,SERVICEID,VEHICLEID)
  SELECT
      1161,
      1783,
      'Mileage',
      1,
   ...

SELECT '123567*' + Space(41-8)+ left(cast(ltrim(rtrim(Interest)) as varchar (7)) + Space(6), 7)+ Space(89-49) + '000'+ '0000123456' as String

It'd be interesting if the current poster would cluster his table on ( ColA, ColB ), then run the original queries.  The results will be vastly better than before, and...

If you (almost) always query by COLA or ( COLA, COLB ), then cluster the table on ( COLA, COLB ).  Then you'll always get a seek with either of those searchesm,...