Selección de una base de datos basada en una lista de pares únicos

Creo que Postgresql tiene la solución más elegante:

SELECT  *
FROM    T
WHERE   ("Key", "Value") IN (('B', 'Alpha'), ('A', 'Charlie'));

Ejemplo de SQL Fiddle

En SQL-SERVER 2008 y en adelante, puede usar VALUES para construir tus tuplas:

SELECT  T.*
FROM    T
        INNER JOIN
        (   VALUES
                ('B', 'Alpha'),
                ('A', 'Charlie')
        ) v (Key, Value)
            ON v.Key = T.Key
            AND v.Value = T.Value

Ejemplo de SQL Fiddle

O para un procedimiento, podría crear un tipo de par clave-valor y pasar esto como un parámetro:

CREATE TYPE KeyValuePair AS TABLE ([Key] VARCHAR(1), [Value] VARCHAR(7));

DECLARE @T AS KeyValuePair
INSERT @T 
VALUES
    ('B', 'Alpha'),
    ('A', 'Charlie')


SELECT  T.*
FROM    T
        INNER JOIN @T v
            ON v.[Key] = T.[Key]
            AND v.Value = T.Value;

Ejemplo de SQL Fiddle

Para MySQL, creo que es posible que deba compilar esto usando AND/OR

SELECT  *
FROM    T
WHERE   (`Key` = 'A' AND `Value` = 'Charlie')
OR      (`Key` = 'B' AND `Value` = 'Alpha')

Ejemplo en SQL Fiddle

Mi conocimiento de otros DBMS es limitado, por lo que si no es uno de los anteriores, lo siento, no puedo ser de más ayuda.

EDITAR (Con la ayuda de a_horse_with_no_name )

La sintaxis de PostgreSQL también funciona para Oracle (y creo que DB2)