There are a couple of things to be aware of. First, the reason the IBUs change when you change your efficiency isn't so much that IBUs are dependent on wort gravity (it's not, it's more "break material" per John Palmer) but that your SG/IBU ratio changes slightly, so it takes more bittering to "cover" the extra bit of sweetness.
I hope that makes sense. Think of it this way. Say you had a beer with an OG of 1.050 and 50 IBUs. That will be firmly bitter (an IBU/SG ratio of 1.000). If you had a beer with an OG of 1.039, 50 IBUs would be undrinkably bitter (IBU/SG ratio of 1.29!), and if you had an OG of 1.099, 50 IBUs would be on the sweet side (ratio of .325!).
In other words, by itself, the IBU number is meaningless. 50 IBUs may be a lot, or it may not be enough. In a blonde ale, it'd be way too much. In a RIS, it wouldn't be enough.
In the case where you're asking about 36 vs 39 IBUs, the difference is negligible. The human tongue probably can't perceive differences of 5 IBUs or so. But it depends on the beer- in a 12 IBU beer, 5 IBUs is alot. In a 40 IBU beer, it's not.
If your IBU/SG ratio is in the ballpark for the beer style you're making, then it will be fine. The key is balance. With the IBU scale, it's helpful to look at those IBUs. But you have to consider the beer style and what IBUs need to be to balance the sweet malt properly.