Verify assumes the thing you're checking has a truth value: "The application is running" is either a true statement or a false statement, so you can say "Verify that the application is running." "The application output", on the other hand, is neither true nor false, so "Verify the application output" doesn't really mean anything, unless you're using "application output" as shorthand for "The application output is correct."
Check, on the other hand, makes no assumptions about what you're looking at. It could be a true/false thing, or it could be a collection of things with no single truth value, such as a quiz with 7 correct answers and 3 incorrect ones.