I am rooted and couldn't find any reference to my problem app in the data folders, just like you guys. I went on the desktop version of the play store and grabbed the package name of the app (it's in the url). Then I opened adb and input:
adb shell rm -R -f /data/data/<packagename>
Now I can...