Magento – Programmatically check is specific coupon is valid for product

The following answer is just theoretical. I haven't tested it, but it seams the way to go.
You can get the cart rules that were applied to the order you cancel like this:

$ruleIds = explode(',', $order->getAppliedRuleIds());

Then you need to get the rules applied:

$rules = Mage::getModel('salesrule/rule')->getCollection()
       ->addFieldToFilter('rule_id', array('in'=>$ruleIds));

Then loop through the rules and try to apply the coupons to the quote.

foreach ($rules as $rule){
    if (!$rule->getCode()) {//skip rules without codes
        continue;
    }
    //normaly there should be only one rule that gets here since you can apply only one coupon code
    $quote->setCouponCode($rule->getCode())->collectTotals()->save(); 
    $quoteCouponCode = $quote->getCouponCode();//get the applied coupon code from the quote
    if ($quoteCouponCode){
        //$rule is valid and $rule->getCode() is a valid coupon code
    }
    //remove the coupon code from the quote if you want
    $quote->setCouponCode('')->collectTotals()->save(); 
}

There is a chance that even for a valid coupon you will get the 'not valid' result. This may happen if you just reached the coupon usage limit (per customer or total) or if you reorder after the expiration date of the rule.

Here's an approach that I took to put in a better error message for two specific filters: the from date and to date.

Those filters are pretty simple compared to digging into the actual rule conditions such as subtotal, as you've mentioned in your question, but I think still provide a significant usability improvement with a pretty straight forward implementation.

There are two pretty clean rewrites that can be done to accomplish this.

Mage_SalesRule_Model_Resource_Rule_Collection::addWebsiteGroupDateFilter

Overload the addWebsiteGroupDateFilter method to prevent rules that don't match the date filter from being excluded entirely from the rules that are processed.

public function addWebsiteGroupDateFilter($websiteId, $customerGroupId, $now = null)
{
    parent::addWebsiteGroupDateFilter($websiteId, $customerGroupId, $now);

    $where = $this->_removeDateFilters();
    $this->getSelect()->setPart('where', $where);

    return $this;
}

protected function _removeDateFilters()
{
    $where = $this->getSelect()->getPart('where');

    foreach ($where as $index => $whereLine) {
        if (strpos($whereLine, "from_date is null or from_date <") !== false) {
            unset($where[$index]);
        } elseif (strpos($whereLine, "to_date is null or to_date >") !== false) {
            unset($where[$index]);
        }
    }

    $where = array_values($where);

    return $where;
}

Clean_Checkout_Model_SalesRule_Validator::_canProcessRule

Overload the _canProcessRule method to check the dates and add a specific error message to the session.

protected function _canProcessRule($rule, $address)
{
    if ($this->_isRuleExpired($rule, $address)) {
        return false;
    }

    return parent::_canProcessRule($rule, $address);
}

protected function _isRuleExpired($rule, $address)
{
    if ($rule->getFromDate() && date('Y-m-d', time()) < $rule->getFromDate()) {
        $message = "This coupon won't be active until {$rule->getFromDate()}";
        Mage::getSingleton('checkout/session')->addUniqueMessages(new Mage_Core_Model_Message_Error($message));

        return true;
    }

    if ($rule->getToDate() && date('Y-m-d', time()) > $rule->getToDate()) {
        $message = "This coupon expired on {$rule->getToDate()}";
        Mage::getSingleton('checkout/session')->addUniqueMessages(new Mage_Core_Model_Message_Error($message));

        return true;
    }
}