If I give a check to someone (as a gift) and I change my mind, am I halachically allowed to cancel it, or do we say that the check is a shtar, and by signing it is considered as if I gave him the money?
Based on the legal definition of a check it would seem to me that it is alot more than just a piece of paper, and you have no right to cancel it.
I would argue that part of the institution of check-writing is the understanding that one may cancel the transfer of funds at any time up until the funds have actually been drawn. Keep in mind:
If a dispute arises over the legitimacy of the check itself, or if one decides to cancel a gift, then one has that right. I think that in many cases, like this one, Halachah would follow the normative practice with regard to the vehicle used to transfer the funds.
The check is NOT a contract. I cannot execute a purchase of real property by writing "Property purchase - 123 Main St., Anytown, IL 12345" in the memo line of a check without a separate, fully binding contract dealing with said purchase. A mere phone call to the bank would override whatever is written on the check.