After asking this question, I got to thinking about why a certain query was doing all the problems.
In short, there was a query which took 500ms, I ran some execution plans and applied the recommended indexes but it only cut off about 50-60ms.
After running it again I found out that the following query(which occur in multiple locations) was really slow:
SELECT @TempCardNumber = CardNumber FROM Cards WHERE (CardNumber=@CardNumber or FullCardNumber=@CardNumber)
When I changed it to be
SELECT @TempCardNumber = CardNumber FROM Cards WHERE (CardNumber=@CardNumber)
It ran super fast, and even the removal of indexes didn't matter too much, leading me to believe this was the main bottleneck, but I don't understand.. whats so wrong about it?