I'd break the SEM plan down into:
- PPC (which you have covered, and others have commented on)
- Affiliate advertising (if appropriate for your site)
- General advertising (banner ads, sponsorships, etc)
- Viral marketing (largely link building, but can be focused on one off promotions)
- Press releases (online and offline)
- General link building
- Competitor research (I find it useful to do this first - nice way of building some ideas)
- RSS feed marketing
- Partnerships / Business Development (is your site compatible with other, non-competitive sites? Can you take advantage of this?)
- Research (Are there any product lines that you could be offering that you currently don't? Are there any keyword areas you could be targeting that you currently don't?).
- Email marketing strategy
- Content writing / generation
I'm sure there's tonnes of other stuff that can also be added to the strategy (tagging, social networking, etc).
The thing about search engine marketing is that it really should encompass all areas of online marketing - it's all related and should be treated as such.
For example, you might not think that email marketing directly affects your search engine positions, but what if a successfull email campaign results in a quantity of organic links?
Or, what if Google decides not to like you for a few months? Surely other areas of online marketing should be part of the mix to bring an element of stability to your business?