Selecionando de um banco de dados com base em uma lista de pares exclusivos

Acho que o Postgresql tem a solução mais elegante:

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

Exemplo do SQL Fiddle

No SQL-SERVER 2008 em diante você pode usar VALUES para construir suas 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

Exemplo do SQL Fiddle

Ou para um procedimento, você pode criar um tipo de par chave-valor e passar isso como um 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;

Exemplo do SQL Fiddle

Para MySQL, acho que você pode ter que construir isso usando AND/OR

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

Exemplo no SQL Fiddle

Meu conhecimento de outros DBMS é limitado, portanto, se não for um dos acima, desculpe, não posso ajudar mais.

EDITAR (com a ajuda de a_horse_with_no_name )

A sintaxe do PostgreSQL também funciona para Oracle (e acho que DB2)