To everyone who recommended the articles on dynamic SQL, thank-you. That is an elegant solution which I had missed due to my hard-wired "Dynamic SQL is Bad" thinking.
I also had a play around with using CTEs to evaluate each condition at the start and then join the results back together, but I haven't been able to get onto a decent sized data set to play with the idea.
The example below assumes a unique key (column name is "Id") exists on the Person table which is not related to their first and last names
FN AS (
WHERE FirstName LIKE COALESCE(@l_FirstName, LastName)
, LN AS (
WHERE LastName LIKE COALESCE(@l_LastName, LastName)
INNER JOIN LN
ON FN.Id = LN.Id
Anyone care to test this on a sufficiently non-trivial data set?
Edit: And yes, I'm sure that full-text indexes would simplify the situation. However, the original article (thanks again for posting Tony) was more about boolean algebra and I was trying to offer an alternative structure for that.