it's not really about adding or not adding the lag.
the game does have it's share of slowdowns by default but mostly they're caused by dumping multiple 3d things on the screen at once, I noticed that battles with 4 members and 4 enemies tend to mostly suffer from that. Nonetheless, I do spin the game on actual hardware everytime I make changes to ensure that it still runs atleast at it's original performance rate, and i did give it a spin on the devkit's performance analyzer once too, just for shits'n giggles. Changing the graphics from 16 to 256 colors isn't much of a change as far as the game dealing with it goes, sans the fact that the filesizes (especially on small images like 12x12 pixel icons) gets large really fast due to the palette eating tons of space. Going from indexed to direct color would propably introduce a nice lag though (again, the gim library is awful.)
same thing appeared with the ps1 soundtrack, which i originally re-encoded to 128kbps against the original 64kbps, but it became practically unplayable slow on real hardware so i gave up on that and just left it at 64kbps at the end.
i think in general the devs were just being overly careful with the files trying to shave off as much as they could at the cost of little visual candy (like the character portraits that were encoded to 128 colors by default.)
at the end of the day i'll do some optimizing with it once i know for a fact that im done with the graphics, since making things like 32-color gim files is completely possible regardless of the fact that sony's official tools for making them only support 16, 256 or direct color. I just added an extra step to trim the files back to any palette size i want. The gim library itself supports this just fine, it's just the conversion tool that doesn't.
for those working on psp stuff and interested of this extra little optimization, practically you make your image 32 colors, then you make it to 256 colors, order your palette so that the first 32 entries of the palette are used, and then convert it to 256 color gim, and then change the palette entry count from the gim header and delete the end of the palette which should all be 0x00000000 (or which ever your tool of choice uses as not used color) The gim library games use supports this 100% and honestly i have no idea why the conversion tool itself doesnt. I've been planning on making my own for that purpose because messing with the hex editor is a little annoying.
All in all it's not a big deal but my inner perfectionist always shrugs when i see an image that has 0x100 worth of data and 0x400 worth of palette in it -.- not want!
as far as the "quest complete" i might just give it a little glowy outline like the original has just to add some mass into it, but dunno... we'll see, Im still in progress of playing with the final look of the graphics anyway.
edit: here's a tiny bit more orange one with a glow around it like the original (sorry, still no line
edit2: slightly stronger glow (transprency nicely eats palette entries