Normal behavior is subjective to your implementation. If failed payments aren't returning properly to your site it usually means the cancel URL was not constructed and given to the gateway so it can return to a specific baskets cancel URL, which will redisplay the basket to select a new payment method. This is typically done with the below API call inside of a gateway.

What transaction id you send to the payment gateway is entirely up to you. CBSubs does not generate new invoice ids on payment failure or cancellation. If you need to do such a thing take a look at our Quickpay implementation which ensures an invoice id set to the payment provider is always unique (even for cancellations and failures).

What could be wrong?

I don't know. I didn't create the gateway you're using. What your gateway does during a cancellation is entirely on the implementation. If it's a hosted payments gateway that's extending the cbpaidHostedPagePayHandler class then the handleCancel function is called to deal with cancels. Typically you need to put the basket in a RedisplayOriginalBasket state during cancel for hosted payments. Take a look at Quickpay for an example as it's a pretty minimal gateway implementation.