Computed Column + Full-Text = Fail

I'm trying to figure to figure out the best way to query our database for

One of our developers is implementing a "global search" feature on our intranet. The idea is that a single search string will query multiple columns in a table. For example, searching for "mike fedex" would return the following records:

company | firstname | lastname | notes
FedEx | Mike | Smith | this guy is cool
Paint World | Mike | Anderson | Used to work for FedEx

but not:
Bodum | Mike | Easton | I like apples

because it does not contain all of the search terms.

I tried to create a computed column on our "contacts" table that simply concatenated all of the fields I wanted to search. The idea was to then use CONTAINS or CONTAINSTABLE on the computed column like this: SELECT... WHERE CONTAINS(computed_column, 'word1 AND word1 AND word3'). That would work great, until I realized you can't add a computed column to your full-text index.

Pain.

Any suggestions?

EDIT: The magic sauce needs to be able to search multiple terms across multiple columns with no concern for the order of the words in the search term. For example, searching for "Please Help" and "Help Please" would return the same results. Using LIKE '%Please%Help' and LIKE '%Help%Please' would return very different results.