OK, I can confirm this is an issue. Deleting games with backup managers in certain instances (yet to be determined), will not recover HDD space and you'll effectively be left with a blocked up PS3 that just says, "sorry, I've got no room left to start this game!"
Furthermore, it seems that if you go looking for what is taking up all the room, you won't find it. Comgenie, FTP - don't help.
In my instance, I have used many versions of payloads and backup managers FTP and the rest to install games since October last year. I hit the wall installing two games one after the other last night. First indication was a window on the XMB saying my PS3 had less than 500MB free. I went to start one of the games I installed. It wanted to update. When I tried to update, it said it needed more space than was available so quit back to the XMB. I deleted a game (whilst on payload Hermes 4b 3.50 spoof), with multiman (current version), and tried again but no change.
I deleted another game that I recalled installing with Open Manager, with the same. Tried a small game (Borderlands), it said it needed another 35mb free to be able to start. Deleted two more games. Still nothing.
Booted up Comgenie to see what I was missing - could not find any reference to the games I deleted. Same with FTP and yet the PS3 is saying it full to the brim.
I note @Mathematician's comment above. Whilst searching for a solution I cliked on update in Multiman and it indicated that my 3.41 version might be the first one. Did not update to the second - unsure whether doing it by this means was safe.
Other than that, I'm presuming I've got great swathes of corrupt data or something in the PS3 is reading wrong paths and needs to be reset.
As suggested above I will try PL3 payload tonight but don't hold out much hope of anything other than a full reformat.
Anyone got any other suggestions or workarounds?
"We all agree your theory is crazy, but is it crazy enough?" - Neils Bohr