Custom Post Rewrite Nirvana

Custom Post types are a great addition to wordpress however i’m struggling to find a way to achieve nice urls that use custom templates depending on the post type:

Part 1

example.com/customposttype
Should display an index of recent customposttype posts

example.com/customposttype/archive/page/2
Should display an archive of customposttype posts

example.com/customposttype/category/cat_name
Should display an archive of customposttype posts in the given category

example.com/customposttype/tag/cat_name
Should display an archive of customposttype posts with the given tag

example.com/customposttype/search/
Should display search results for customposttype posts

Part 2
…so thats stage one, part two involves wp using custom template files to render these pages base on the customposttype.

e.g.

• index-customposttype.php
• archive-customposttype.php
• category-customposttype.php
• tag-customposttype.php
• search-customposttype.php

I’ve searched high and low for methods to do this. Found a good plugin to do archive pages, simple-custom-post-type-archives, but a job i’m working on really needs the search and category pages.

If anyone has any idea on how to go about supporting this please let me know.

Thanks,