Hmm. The BeBook doesn't exactly make this clear! [and I can find no reference at all in the Haiku Book]. "pathname can be absolute or relative; if it's relative, it's reckoned off the base path specified by the ADDON_PATH environment variable." Which doesn't really sound like a search... [Guess that's why BeOS apps don't seem to do that!]
ArtPaint actually does its own search, using absolute paths. Unfortunately it takes no account of PM, so it only looks in the read-only directories -- a bit useless at the moment.
Looking at the actual ADDON_PATH, though, the leaf-directories all seem to be "add-ons". Obviously ArtPaint add-ons would have to be in an ArtPaint subfolder -- except for the local folder! So it wouldn't be quite automatic.
Anyway, not a complicated fix!