As per Pounding A Nail: Old Shoe or Glass Bottle?:
This is quite possibly the worst way
you could store this data in a
database. No, seriously. They had
better ways of doing this over thirty
years ago. You have created a horrible
problem that is only starting to rear
its ugly head. It will only continue
to get horribly worse, costing your
company more and more money to
maintain.
The answer is to make a new table, with a one-to-many relationship between the main ID and the different values. Then it's a much simpler query:
SELECT MainID
FROM NewTable
WHERE FieldA = @Value
This is a much easier solution to code against, not to mention understand. And it will help significantly when you have to join this table to others.
EDIT: From your responses, I understand that doing this would be a serious amount of work. However, you're already running into the issues that are arising from the current setup. Doing this will take time up front, but it will make future development significantly faster in the long run.