My first ever post. Here are my 2 cents:

1. Sotiris' article has some good acdemic interest.  But just as laperrej pointed out, we can't use anything like that in production because of performance issues.
2. AKM's answer is not a bad one, for a large, busy system. I would actually push it futher: use a master stored procedure to call sub stored procedures. Yes, it would be lots of typing. But performance is always the key.
3. Dynamic construct a query is not a bad idea. When you use EXEC sp_executesql @CMD, the plan is most likely cached and reused. Comparing with executing a wrong plan, the time consumed to generate a plan is neglectable
4. If I am tasked to write such a query, I would do this:

CREATE PROC usp_GetComstomers

@CompY VARCHAR(100)='%',

@ContY VARCHAR(100)='%',

@CompN VARCHAR(100)='NoNothingNoneWhateverString',

@ContN VARCHAR(100)='NoNothingNoneWhateverString'

AS

/*

Example:

EXEC usp_GetComstomers '%','Germany','A%'

EXEC usp_GetComstomers '%the%'

*/

SET NOCOUNT ON

SELECT *

FROM dbo.Customers

WHERE CompanyName LIKE @CompY

 AND Country LIKE @ContY

 AND CompanyName NOT LIKE @CompN

 AND Country NOT LIKE @ContN

This would be fast and not too bad looking. 🙂