An user is in my app and making a transaction to my BTC address and claiming that he has made the transaction. Now I have to verify whether it is his transaction or someone else's that he is claiming to be his. . .
You should be generating a new receiving address for every transaction.
This way you know exactly who made the payment, since you only provided the payment address to a single person. You know exactly what theya re paying for, because you supplied that address for a specific payment of a specific set of products or services.
If this is not how you coded your app, then you are doing it wrong.