If you're using IMAP, on the "Incoming" tab in the account's properties, make sure "make all messages available" offline is set and make sure you're not using "low-bandwidth mode" or "do not downloaded attachments".
That will make it so Opera fetches everything at once so that Opera doesn't have to download anything when you open any of your messages.
As for fetching headers, Opera should do that for all messages when you first set up the mail account. After that, it'll only do that for new messages and it should take a long time unless you have thousands of new messages coming in at once.
With POP, just make sure "low-bandwidth mode" is off.
What it sounds like you're talking about is the time it takes to load the database.
Close down Opera and edit operaprefs.ini in the preferences folder (see help -> about Opera Mail for the location). Under the Mail section, add/set:Load Mail Databases Asynchronously=0
That should make the mail database load way faster. But, it there will be a few second delay before the UI loads. Should be way better than what Opera Mail is doing now.
Also, in accounts.ini in the mail folder, while Opera is closed, change the "Initial Poll Delay" for each account to 1.
Another thing you can do is defrag your mail folder. While Opera is closed, defrag your hard drive or move the mail folder to another drive and then move it back.
If all else fails, you can fix your mail folder, which will help for a while. But, fixing the mail folder is a pain. However, it might be something that you have to do if the cause of the slowness is a corrupted mail folder.
Another thing you can do for IMAP is to delete the IMAP account and add it back in. That should at least make things fine for that IMAP account as long as the database isn't too messed up.
Also, you can delete the "lexicon" folder in the mail folder so that Opera rebuilds the search index when it starts back up. This might help with making searching faster/more correct.