Ideally you draw with the palette restrictions in mind, rather than drawing an image, and then trying to constrain it to palettes.
It's much better to let artists choose their own limitations during the creation process, and just create the final product by exporting/converting.
So which suggestion should I take?
These advices are not mutually exclusive. You definitely should draw with the restrictions in mind. Using unrestricted software doesn't mean drawing photorealistic images expecting them to convert well to NES specs. One thing you can do, for example, is enable a 16x16 pixel grid in Photoshop (or whatever software) when drawing backgrounds, so you can easily tell if you're respecting the attribute limitations, but you'll still have layers (for keeping trees, bushes, etc. separate in case you need to move them later), transparency (for onion skinning of background animations, for example), and whatever other features you find useful as an artist. In photoshop you can also use smart objects for tiles, metatiles, or repeated elements in general, meaning that changing 1 instance will automatically affect all others. When you're done, you can export the final image for conversion, but still keep the editable (layered) version for future tweaks that might be needed.
What route you'll take will depend on how you like to work as an artist. Most artists already have an established workflow, and they'll definitely be more productive if they can maintain that workflow. If they're targeting an specific console, they should definitely keep the limitations in mind, knowing that the final result should strictly conform to them, or deal with any degradation introduced by automated conversion. If you're new to this, doesn't have a workflow, and just want to plot pixels, then by all means, draw all your graphics in YY-CHR or something, where you'll be constrained to tiles and palettes all the way.
Let's find out how did they make those complex backgrounds.
I'm pretty sure that the artist is more important than the tools. A good artist will make do with the crappiest of tools, but not even the best software in the world will improve the work of a bad artist. Hunting down the obsolete computer and floppy disk with the software they used to make the Nekketsu games will NOT instantly allow you to draw the same kind of graphics (just like using the same assembler used for SMB3 will not instantly allow you to create an engine as good as that game's), but if you study the graphics well and really understand what makes them any good, you'll probably be able to create similar art no matter the software. Most artists will prefer to use their tools of choice though, in order to achieve the best possible result in the smallest amount of time.