When integrity of an Exchange 2013 mailbox database is questionable, is it safe to simply "move" the mailboxes, or do they have to be exported?

There is no size limit for mailboxes with the New-MoveRequest command.

I would highly recommend using this tool before trying to perform an export/import of PSTs. Move requests are very simple, and are easier to work around errors with. PST exports can be effective for certain scenarios, but then you have to deal with multiple steps instead of one step and the risk of large PST corruption.

The only problem that you may end up with is corruption of individual items within some mailboxes. This is not uncommon, and can be worked around by raising the limit on how many corrupt items you want to allow to be skipped (not migrated) before the move operation fails.