I have two mail servers and would like to make use of greylisting, but am not sure if this simply works with two servers. E.g. when a sender gets greylisted and uses the second server for the second attempt, leading to a second greylisting, will it be sent again or should I rather use the same greylist for both servers?
Both options are bad.
Option 1 - One greylist instance on each MX entry
Has the charm of reduced complexity as you do not have to configure a shared database where all MXes have to sync their findings.
The problem is that if you configured your MXes with the same priority then you can't determine where the next legitimate delivery attempt will go to. So if one IP passed on one MX it still has to pass on the others. This will introduce more delay.
If you instead configured your MXes with different priority all legitimate servers try on the first one. This is a better setup.
Option 2 - One shared greylist instance for all MX entries
This is a good idea as with a shared database you have shared knowledge. If one IP passed on one MX then the other MXes benefit and this IP can pass on them, too.
The problem here is, that you need a good greylist algorithm and software for this setup. As you defer delivery on the first MX everybody tries the next MX (MTAs and spambots!). But this should not count as a successful pass of the greylist because then you let even spambots pass. In this case the greylist algorithm has to rely on the time between first and current attempt and not on the overall attempt count.
If that would be my server I won't have multiple MXes. One is enough. For all those who want redundancy I would choose one MX with a HA-cluster behind that one IP. On each HA-node you can then run a shared greylist instance where all the negatives of option 2 are gone.