Different companies are different. I would suspect the usual case is that they would check, but they'd be looking for things such as a negative employee record and adverse conditions on the termination of the arrangement. For example, if you threatened your former boss when you left, they'd make note of that and probably not offer a job. But if you left for normal reasons without a scene, or you had a very good reason for leaving, such as they were looking at shutting down that office, there wouldn't be a problem from that.
However, as I'm not in HR, I can only say for sure about the two companies whose processes in this regard were clearly notable:
One of them did not check at all. Six months after firing someone for a variety of things including workplace violence and threats of violence, they hired him back at another location and had to go through the whole thing again.
One of them does the check for former employment regardless of what you filled out on your application. If there's a mismatch between your application and the results of that check and there's no clear room for confusion, any offer is rescinded (failed background check.) If there's room for ambiguity, they call to discuss it. I had a coworker who'd gotten such a call before he was hired - he hadn't known about one of the company's acquisitions.
It's possibly worth noting that employees are generally allowed to pursue other jobs. If a company feels the need to explicitly state that employees are allowed to pursue other jobs for some reason, I'm pretty sure this means "we will have no ill will regarding your departure should you leave at this time giving proper notice and without causing a scene." It could even mean, "We really do not want to fire anyone but we have too many people working here to keep this store open, so rather than having layoffs, we're just laying this out there and hoping some people will find other jobs and thus reduce our headcount. Thanks."
TL;DR: Your prior employment with them should not provide any obstacle to your future employment with them, based on what you've said.