No, I was talking about the user's Library (~/Library) and not the general Library (full path /Library). I just did not explicitly mentioned ~/ because for me that is default (if you start from your home directory, Library and ~/Library are the same).
What I did find out that the whole cookie process is now managed via a daemon (cookied) which apparaently keeps its own data somewhere in the general systems area.
I wonder how 'private' 'Private Browsing' really is, and I suspect the cookies are stored anyway, they are just outside of reach of the Safari processes that may need/use them. And then there are the plugins that may or may not respect the 'private browsing' settings. Suppose you are under a dictatorship and you want to remove traces you have visited some opposition site, I would not trust 'Private Browsing' against good forensic snooping and I would only trust the removal of data if it is also wiped (not just unlinked)). Hence, I would always want to know where the data is really stored so I can wipe it instead of unlinking it.
I tried from a Guest user and noticed that just starting Safari which opened a standard Apple page added a cookie for fbcdn.net (Facebook) and apple.com. At some point I had a cookie for macrumors.com which did not go away, not even when I completely reset Safari, not even when Safari had no windows open and Private Browing was turned on. I suspect there is some complex interplay between 'saved application states', the system-wide cookie daemon cookied and its data, and more, all leading to a system that is not really private and where data cannot be removed.
I was not removing the data while Safari was running. I would quit Safari first and then remove it.