Simplifying data search using .NET

An example on the asp.net site has an example of using Linq to create a search feature on a Music album site using MVC. The code looks like this -

public ActionResult Index(string movieGenre, string searchString)
{
    var GenreLst = new List<string>();

    var GenreQry = from d in db.Movies
                   orderby d.Genre
                   select d.Genre;

    GenreLst.AddRange(GenreQry.Distinct());
    ViewBag.movieGenre = new SelectList(GenreLst);

    var movies = from m in db.Movies
                 select m;

    if (!String.IsNullOrEmpty(searchString))
    {
        movies = movies.Where(s => s.Title.Contains(searchString));
    }

    if (!string.IsNullOrEmpty(movieGenre))
    {
        movies = movies.Where(x => x.Genre == movieGenre);
    }

    return View(movies);
}

I have seen similar examples in other tutorials and I have tried them in a real-world business app that I develop/maintain. In practice this pattern doesn't seem to scale well because as the search criteria expands I keep adding more and more conditions which looks and feels unpleasant/repetitive. How can I refactor this pattern?

One idea I have is to create a column in every table that is "searchable" which could be a computed column that concatenates all the data from the different columns (SQL Server 2008). So instead of having movie genre and title it would be something like.

if (!String.IsNullOrEmpty(searchString))
{
    movies = movies.Where(s => s.SearchColumn.Contains(searchString));
}

What are the performance/design/architecture implications of doing this?

I have also tried using procedures that use dynamic queries but then I have just moved the ugliness to the database. E.g.

CREATE PROCEDURE [dbo].[search_music] 
    @title as varchar(50),
    @genre as varchar(50)
AS

-- set the variables to null if they are empty
IF @title = '' SET @title = null
IF @genre = '' SET @genre = null

SELECT m.*
FROM view_Music as m 
WHERE 
    (title = @title OR @title IS NULL)
    AND (genre LIKE '%' +  @genre + '%' OR @genre IS NULL)
ORDER BY Id desc
OPTION (RECOMPILE)

Any suggestions? Tips?