Based on your last comments, this looks like the only way that might really help. Your keys columns are exceptionally non-selective, which makes it more difficult to get best performance.
(DATASOURCE, DATAAREAID, PARTITION)
SQL DBA,SQL Server MVP(07, 08, 09) A socialist is someone who will give you the shirt off *someone else's* back.