As of a couple of years ago, Accessibility APIs were not available from within the OS X sandbox, but that might have changed. It is more likely, however, that those apps managed to get a special exception from Apple, and that they have additional sandboxing entitlements that partially break them out of the sandbox just enough to let them use the accessibility APIs.
What you should do is first file a bug via bugreporter.apple.com, telling what you're trying to do with accessibility and why, and asking them to give you a sandboxing exception. If they approve the exception, they will probably give you a custom bit of sandbox profile language code that makes it possible to call the accessibility APIs from within the (somewhat weakened) sandbox.
With that said, depending on what you're doing, don't be surprised if Apple says, "Sorry, that app doesn't fit the app store model. Please sign your app using Developer ID with sandboxing disabled, and distribute it outside the store."
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…