In-camera formatting involves writing data to the flash card. Whenever a flash card writes new data, it must first erase an existing flash page and then write new data to it. The flash card maintains some extra pages (usually pre-erased) to make this faster. However, if there are not enough pre-erased pages to handle a series of writes, performance slows way down while it erases pages.
In some cases, it may even need to evict existing data so that it spreads the erasures out over more flash pages, because you can only erase a flash page so many times.
For flash cards that start out full, there are many fewer free pages than there were when the flash card was new, which is one reason why flash cards tend to be slower the second time around. (The other reason has to do with the way signals are encoded in each flash cell, but this tends to be a much more gradual degradation in performance.)
Either way, there are only a certain number of spares. The more spares, the faster the card can write new data.
If you know whether your flash card's NAND flash erases to all zeros or all ones, you could ostensibly write all zeros or ones across the card so that no block will require an erase when you write data to it next. This is because a flash page only has to be erased when bits change in one direction and not when they change in the opposite direction. (The details depend on the flash part and on how the controller is configured.) Of course, realistically, you can never be sure, so this is probably not the best approach.
Another, better solution is to send the right SD card commands (CMD32, CMD33, and CMD38 with appropriate delays in between) to erase all of the flash pages, assuming your flash card supports those commands. This will dramatically improve performance. However, depending on whether the flash card does the erasure synchronously or asynchronously, it could take a long time.
It is possible that the SanDisk card supports the SD erase commands, and that your camera is using it, and that this is the reason for the extra time. If so, the SanDisk card will be much faster than the Lexar after reformatting.
It is also possible that the Lexar card supports the SD erase commands, and that your camera has used them to wipe deleted files, resulting in more free flash pages ready for new data, thus making the format faster because it doesn't have to wait for a slow erasure. In that case, the Lexar card will be much faster after formatting
Obviously none of this really tells us for sure what's going on—you'd probably need a proper bus analyzer to be certain—but maybe it at least gives you a vague idea of some of the issues that might be involved.
And it could be something else entirely, such as the SanDisk card doing more wear leveling than the Lexar, or something else that I've forgotten.
Either way, I wouldn't worry about it.
