You are right, only backups made from the organizer can restore a backup folder to a new computer or drive while keeping the links to the new location of the media files.
If you have a backup of all your files, you may have a way to recover your catalog folder. It's a folder containing a file named 'catalog.pse9db' file. Using that catalog folder would result with all media files disconnected as you correctly imagine.
Using PSE9 or a newer version would not make a difference, you would have to 'reconnect' your files, which is not strictly impossible, but would require a lot of efforts and time.
As Michel says, it is quite possible but a little time-consuming to reconnect all of your media files.
You have not told us about your new computer setup. Is it another laptop or a desktop? I ask because if you have more than one internal drive on a desktop, it would perhaps be possible to restore the external backup to an internal drive and then copy the catalog folder mentioned by Michel to a default location on the new computer's OS drive (C:). Depending on your media folder structure on the old computer, you may then be able to recreate it on the new machine by copying the folders to the new drive C. That would at least avoid the problems of disconnected files. If you have a new laptop, this strategy would also work by restoring the backup to another external drive. However that would take a little longer.