I have a table in a DB that will be accesed often.
The problem is Im unable to cluster the table on the field that Im searching for and in order to perform the query the DB has to scan the entire table. Lets assume that this table will grow to include a million records.

Is this going to be a problem performance wise? Is it safe to say that you cant have an "enterprise" level app with the above schema?

You can't even have a 'moderate' level app with large table scans. Even at 100k rows or so, you will see a serious slowdown. Table-scanning a million with any frequency will cripple pretty much any box.

So... what are you scanning for, anyway?

I'm curious as to what sort of field wouldn't allow you to cluster a table.

What indexing techniques have you tried? Full table scans are usually the result of either missing or badly configured indices or poorly tuned SQL.