How do you restrict AMI use with IAM using Deny and NotResource

EC2 will authorize multiple resources for the runInstances API including the instance itself. When it authorizes that you have access to "ec2:RunInstances" on instance "arn:aws:ec2:us-east-1:<acct>:instance/instanceID" your deny statement will cause that authorization to fail.

If you only want to have a deny around using an AMI that is not the referenced AMIs, you have to include a condition that is only applicable to an AMI. You can see the list of condition context keys on the Supported Resource-Level Permissions for Amazon EC2 API Actions. Images have an ec2:ImageType context key, so you could restrict the AMIs with the following:

  {
        "Sid": "Variable",
        "Effect": "Deny",
        "Action": "ec2:RunInstances",
        "NotResource": [
            "arn:aws:ec2:us-east-1::image/ami-04681a1dbd79675a5",
            "arn:aws:ec2:us-east-1::image/ami-0ff8a91507f77f867"
        ],
        "Condition" : {
             "Null": {    "ec2:ImageType":"false"}
       }
    }

Note: hand-coded, untested, JSON policy document -- YMMV, but you should get the idea.

This essentially says "Deny ec2:RunInstances on resources that are not the two listed AMIs IF, and only IF, the condition key ec2:ImageType is not null." Which, when the instance is being authorized, the condition will not match and the deny will not take effect.

That said, the best way to achieve what you intend (allow only the use of specific AMIs and specific subnet is to write the policy as follows:

{
"Version": "2012-10-17",
"Statement": [
    {
        "Sid": "ReadOnlyAccess",
        "Effect": "Allow",
        "Action": [
            "ec2:Describe*",
            "ec2:GetConsole*"
        ],
        "Resource": "*"
    },
    {
        "Sid": "Fixed",
        "Effect": "Allow",
        "Action": "ec2:RunInstances",
        "Resource": [
            "arn:aws:ec2:*:*:subnet/*",
            "arn:aws:ec2:*:*:key-pair/*",
            "arn:aws:ec2:*:*:instance/*",
            "arn:aws:ec2:*:*:volume/*",
            "arn:aws:ec2:*:*:network-interface/*",
            "arn:aws:ec2:*:*:security-group/sg-03cf946fca20ef2e2",
            "arn:aws:ec2:us-east-1::image/ami-04681a1dbd79675a5",
            "arn:aws:ec2:us-east-1::image/ami-0ff8a91507f77f867"
        ]
    }
]

This allows the creation of EC2 instances only when the security group is the specified security group and the AMI is one of the specified AMIs.

This takes advantage of the fact that IAM's permission model is "deny by default" - any permission not explicitly allowed in the policy set is denied. With this modified policy allow is only effective when they choose the correct security group and AMI.