Since time immemorial, the Android Market app let you see a list of just your purchased apps under a "Not installed" section. When the Play Store change happened, that list was still there. Then at some point with all the stealth updates, that list of paid apps went away. Thanks to Paul O'Brien over at Modaco, we have the Legacy Play app that solves that problem by bringing back the "Not installed" list.
O'Brien was able to retrieve an old version of the Play Store client and hack around to make it run alongside the official Play Store. In the Legacy Play Store your My Apps screen will again have a handy list of all your paid apps that are not installed on the device. The current version of the Play Store has a tab for all your apps. That's nice, but if you try a lot of free apps, you'll be scrolling for ages just to find the handful of paid apps you want on your device.
You can download the APK at the link below. On pre-Jelly Bean devices it can usually be installed normally. On Jelly Bean and some more temperamental phones with older software, you have to push the installer to /system/app and chmod it to 644. If you have to go this route, root is needed. Is this maybe a little extreme just to return that one feature? Nope. It was insane for Google to remove that in the first place.