For what services can't you do this? I recently made a script that iterated over all DynamoDB Tables, Lambdas, SQS, Kinesis Firehose/Analytics/Streams, S3 Buckets, etc. and added a tag to track cost on the individual services.
The only thing I can think of is that you will not have any data before the data you added the tag on.
- launch instance A
- create a new CAT and activate it in the Billing console
- apply CAT to instance A
- get no cost data back for that instance in Cost Explorer filtering on that CAT
- terminate instance A
- launch instance B
- apply CAT to instance B
- get cost data back for that instance in Cost Explorer filtering on that CAT