OOD: class hierarchy with method arguments forming another hierarchy

I'd like to find out how do you guys handle the following situation: you have a class hierarchy, call it H1, with some polymorphic method that is supposed to accept an argument which type forms hierarchy H2 in the following way: the higher the class is in H1, the higher H2 argument it accepts.

+-----------+           +-----------+
|     A     |           |     A'    |
|-----------+           +-----------+
|method(A') |                 ^
+-----------+                 |
      ^                 +-----------+ 
      |                 |     B'    |
+-----------+           +-----------+
|     B     |                 ^
|-----------+                 |
|method(B') |           +-----------+ 
+-----------+           |     C'    |
      ^                 +-----------+
      |
+-----------+
|     C     |
|-----------+
|method(C') |
+-----------+

Before writing any code I mention that I have two protocol classes with methods check that have much in common, but request parameters are specific for concrete arguments -- transactions. The language is scala, but the problem is language-agnostic. At the first glance it should look like that:

trait BaseMerchantProtocol
{
  def check(transaction: BaseTransaction) = {
    // some common code...
    println(requestParams(transaction))
    // ...and here as well
  }

  protected def requestParams(transaction: BaseTransaction)
}

class SmsCommerceMerchantProtocol extends BaseMerchantProtocol
{
  override protected def requestParams(transaction: SmsCommerceTransaction) = {
    List("result specific for SmsCommerceTransaction class")
  }
}

class TelepayMerchantProtocol extends BaseMerchantProtocol
{
  override protected def requestParams(transaction: TelepayTransaction) = {
    List("result specific for TelepayTransaction class")
  }
}

But of course it does not compile as Liskov substitution principle is violated.

Let's try this one:

trait IMerchantProtocol {
  def check(transaction: SmsCommerceTransaction)
  def check(transaction: TelepayTransaction)
}

class MerchantProtocol extends IMerchantProtocol
{
  def check(transaction: SmsCommerceTransaction) = {
    doCheck(transaction)
  }

  def check(transaction: TelepayTransaction) = {
    doCheck(transaction)
  }

  private def requestParams(transaction: SmsCommerceTransaction) = {
    List("result specific for SmsCommerceTransaction class")
  }

  private def requestParams(transaction: TelepayTransaction) = {
    List("result specific for TelepayTransaction class")
  }

  private def doCheck(transaction: BaseTransaction) = {
    // some common code...
    println(requestParams(transaction))
    // ...and here as well
  }
}

But that won't compile as well -- and with the same reason: doCheck accepts BaseTransaction, but requestParamss have more strict preconditions.

The only thing that I came up with and that works is the following:

class MerchantProtocol extends IMerchantProtocol
{
  def check(transaction: SmsCommerceTransaction) = {
    doCheck(transaction, requestParams(transaction))
  }

  def check(transaction: TelepayTransaction) = {
    doCheck(transaction, requestParams(transaction))
  }

  private def requestParams(transaction: SmsCommerceTransaction) = {
    List("result specific for SmsCommerceTransaction class")
  }

  private def requestParams(transaction: TelepayTransaction) = {
    List("result specific for TelepayTransaction class")
  }

  private def doCheck(transaction: BaseTransaction, requestParams: List[String]) = {
    // some common code...
    println(requestParams)
    // ...and here as well
  }
}

But I don't like that all check methods belong to the same class. How can I split them by classes?