So I've been having this problem for about a year, and after buying a new graphics card to fix the problem, and having it persist, I've finally found the solution. After endless unanswered threads, to which I can only assume a new screen was purchased, I've finally found the fix. The problem is, as this superuser thread suggests
http://superuser.com/a/435994/499645 (If anyone has enough rep there, please post this as an answer to help out other users, as I don't have enough.), that the monitor is giving dodgey information about the visible screen area, resolution, and other display-related meta information. What it doesn't mention, is that this meta-information is called EDID. Turns out that the monitor is giving false EDID information, more specifically, it's giving EDID information for a 720p display, and sometimes even TVs with weird aspect ratios. This results in one, or both, of two things: Your graphics card reads that you want to send it a 1080p 16:9 resolution, but it sees that the screen is, for example 15:9, or something similarly broken (This is when you just can't get the overscanning right); Your graphics card sees that it's sending a 1080 resolution to a 720p screen, and starts taking corners in displaying information in the screen as it won't be visible on a 720p display.
=== THE FIX ===
So what you've been waiting for: AMD offers a peice of obscure software to fix this issue. The UI is a bit odd, but it supports Windows and Linux, and is avaiable here: http://developer.amd.com/tools-and-sdks/graphics-development/amd-edid-utility/
Instructions: TVs usually only have their HDMI sources programmed with broken EDID, but the VGA ports are fine. The issue that this program solves is that EDID is a binary blob that can't really be edited, so what we need to do is copy the correct data from one port to a permanent location, and then tell our graphics drivers to use this data instead of the one supplied by the TV on all ports.
1. Unplug all display cable(s) from your GPU, and plug in a VGA cable from your GPU to the affected TV (You can use a DVI->VGA converter if your GPU has no VGA port)
2. Open up the AMDEDIDUtility and find your monitor (If you have multiple monitors, this process will fix all of them)
3. Click view, then browse a location and save the file. This file needs to stay in the same place, so put it somewhere sensible.
4. Unplug the VGA cable and reinsert display cable(s).
5. Open up AMD Catalyst and set your resolution to 1080p (or required), and fix over-scanning issues with the overscan slider.
6. All done
. You can either repeat this process for any other OS installation, or run the AMDEDIDUtility with the binary file saved (It should be the same for all OS types).