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?

Is there a reason you can't try this out?

Try generating over a million records then running your query and seeing how long it takes. There should be some sort of profiling functionality available that allows you to measure how long it takes to execute a query fairly accurately.