Check if received bitcoin are in blockchain/not pending without a transaction id
It's not how all exchanges are handling this.

Bitstamp is sending bitcoins in batch transactions. That means it is sending your bitcoins to your address and other users' bitcoins to their address in the same transaction.

That means that bitstamp does not yet know the TxId when you submit your withdrawal request.

That is the why.

As for how to solve it, yes you can get a new address for each withdrawal and wait for it to get confirmations. You will not be assailable for transaction malleability, double spending or similar if you do that.