It finds the transaction by scanning the incoming transaction feed on the full node, filtering out interesting ones if they pay the correct amount of satoshis. As soon as a Bitcred is found it logs the user in without waiting for the transaction to be included.
So, basically, it would be cheaper to send a transaction with 0 fee to a node that still accepts these... The transaction probably won't be included in a block, but that doesn't matter?
The transaction needs to exceed the network's min relay fee, otherwise it won't reach the Bitcred nodes. And yes it doesn't have to be in a block for it to verify successfully.