First, we should check the terms of the lease.

Ponieważ przed check jest should.
Bezokolicznik może występować z to, bądź bez tzw. bare infinitive.

PS. W rzadkich przypadkach może wystąpić to po should ale nie jako jego część tylko fragment kolejnego wyrażenia, np.:
One should, to a greater or lesser degree, follow instructions.